广度优先搜索是最简便的图的搜索算法之一,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
深度优先是从一个方向一直尝试下去,直到走不通的时候在回到原来地方继续寻找。而广度优先是通过“一层一层”扩展的方法去寻找目标。扩展时每发现一个点就将这个点加入到队列中,直到找到目标为止。
例如下面这道题,从起点到达终点需要几步?
最开始从入口(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;
}