广度优先搜索(Breadth-first-search),又称宽度优先搜索,简称 bfs,是图的搜索算法之一。与深度优先搜索不同的是,广度优先搜索会先搜索到与起始点距离较近的点,而深搜却是沿着一个分支递归到最后。

bfs

对上图进行深搜按照顶点访问顺序会得到序列:A-B-E-F-C-D-G

对上图进行广搜按照顶点访问顺序会得到序列:A-B-C-D-E-F-G

广搜可以理解为,从起点开始一层一层地往外扩展,内层一定会在外层前面被访问到。

相比深度优先搜索

深度优先搜索用栈(stack)来实现:

  • 1.把起始顶点压入栈中。
  • 2.每次从栈顶取出一个顶点,搜索所有它的未访问相邻顶点,把这些顶点压入栈中。
  • 3.重复执行第二步操作,直至找到所要找的顶点或栈为空时结束程序。

广度优先搜索用队列(queue)来实现:

  • 1.把起始顶点放到队列中。
  • 2.每次从队首取出一个顶点,查看这个顶点所有的未访问相邻顶点,把它们放到队尾。
  • 3.重复执行第二步操作,直至找到所要找的顶点或者队列为空时结束程序。

一般写法

1
2
3
4
5
6
7
8
9
10
11
12
13
void bfs(起始点) {
将起始点放入队列中;
while(队列不为空) {
访问队列元素中队首元素x;
删除队首元素;
for(x 所有相邻点) {
if(该点未被访问过且合法){
将该点加入队列末尾;
}
}
}
队列为空,广搜结束;
}

走迷宫问题

相信大家都玩过走迷宫。用矩阵来表示一个迷宫:

1
2
3
S...
.##T
....

‘S’表示起点,’T’表示终点,’#’表示墙壁,’.’表示平地。你需要从’S’出发走到’T’,每次只能上下左右走动,并且不能走出地图和走进墙壁,请你计算出走到终点需要走的最少步数。

之前问题是求出所有的方案数,需要遍历整张图所有的可能,现在需要求解最少步数,我们依然可以用深搜来遍历所有可能性,然后从中选取最优的步数。但是广搜则不需要搜索所有的路径,由于它的层数具备由小到大的特点,第一次访问到终点时,记录的步数一定是最少的,也就是最优解。所以在“求解最少”这一类问题上,广搜比深搜更有优势。

对于走迷宫问题的广搜,我们把一个格子的横纵坐标用一个结构体(或class)来存储,并放入队列。这里给出一段体现核心思路的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct point {
int x, y;
point(int xx, int yy) {
x = xx;
y = yy;
}
};
void bfs(int sx, int sy) { // (sx, sy) 为搜索的起点
queue<point> q;
q.push(point(sx, sy)); // 将起始点放入队列中
用vis数组标记(x, y)已经被访问过;
while(队列非空) {
取出队列元素(x, y);
for (枚举(x, y)能到达的所有格子(tx, ty)) {
if (点(tx, ty)合法,可以搜索) {
标记(tx, ty)已经被访问过;
记录走到(tx, ty)的步数 = 走到(x, y)的步数 + 1;
q.push(point(tx, ty))
}
}
}
return;
}

更新记录

  • 2018年02月21日 完成初稿