广度优先搜索是最简便的图的搜索算法之一，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
深度优先是从一个方向一直尝试下去，直到走不通的时候在回到原来地方继续寻找。而广度优先是通过“一层一层”扩展的方法去寻找目标。扩展时每发现一个点就将这个点加入到队列中，直到找到目标为止。
例如下面这道题，从起点到达终点需要几步？
题目.png
最开始从入口（1，1）处，一步之内可以到达的点有（1，2）和（2，1），但是终点并不在这两个点上，那只能通过（1，2）和（2，1）这两点继续往下走，那么两步之内能到达哪些点呢？只有（2，2）和（3，1），为了防止一个点多次被走到，这里需要一个数组来记录一个点是否已经走过。
此时两步到达的点事（2，2）和（3，1），可惜终点并不是这两点，所以还要继续往下走，三步能到的点是（2，3）、（3，2）和（4，1），依旧不是终点，所以需要重复刚才的方法，直到找终点为止。
完整代码如下：
#include <stdio.h>
struct note {
int x; //横坐标
int y; //纵坐标
int s; //步数
};
int main(int argc, const char * argv[]) {
struct note que[17]; //应为地图大小不超过 4X4，因此队列扩展不会超过16个
// 记录走过的点，和标记
int a[5][5] = {0},mark[5][5]= {0};
// 定义一个用于表示走的方向的数组
int next[4][2] = {{0,1}, // 向右走
{1,0}, // 下
{0,-1},// 左
{-1,0} // 上
};
int head,tail;
int k,tx,ty,flag;
//队列初始化
head = 1;
tail = 1;
//往队列插入迷宫入口坐标
que[tail].x = 1;
que[tail].y = 1;
que[tail].s = 0;
tail++;
mark[1][1] = 1; //起点已经走过
// 用来标记是否到达目标点，0表示暂时还没有到达，1表示到达
flag = 0;
// 当队列不为空的时候循环
while (head < tail) {
// 枚举4个方向
for (k = 0; k <= 3; k++) {
// 计算下一个点的坐标
tx = que[tail].x + next[k][0];
ty = que[tail].y + next[k][1];
// 判断是否越界
if (tx <1 || tx >5 || ty <1 || ty >4) continue;
// 判断是否是障碍物或者已经在路径中
if (a[tx][ty] == 0 && mark[tx][ty] == 0) {
// 把这个点标记为已经走过，每个点只入队一次
mark[tx][ty] = 1;
// 插入新的点到队列中
que[tail].x = tx;
que[tail].y = ty;
que[tail].s = que[head].s +1; // 步数加1
tail++;
}
// 如果找到目标点，停止扩展，任务结束，退出循环
if (tx == 4 && ty == 3) {
flag = 1;
break;
}
}
if (flag == 1) {
break;
}
// 当一个点扩展结束后，head++才能对后面的点再进行扩展
head++;
}
// tail是指向队列队尾的下一个位置，所以需要-1
printf("%d",que[tail -1].s);
getchar();getchar();
return 0;
}
