第 41 课：广度优先搜索
广度优先搜索（Breadth-First Search，BFS）也是一种用于遍历或搜索图或树（图和树的知识在第 10 章讲解）结构的算法。
在路径规划中，广度优先搜索可以用于寻找从起点到终点的最短路径；在网络爬虫中，可用于遍历网页链接，获取网页信息；在游戏开发中，可用于查找角色周围一定范围内的目标；在社交网络分析中，可用于查找某个节点周围一定范围内的社交圈子等。
广度优先搜索和深度优先搜索的主要区别在于搜索顺序不同。广度优先搜索更侧重于全面地逐层搜索，而深度优先搜索则是沿着一条路径尽可能深地探索下去，直到无法继续再回溯。我们继续通过迷宫的例子来了解广度优先搜索。
41.1 情景引入及建模
走迷宫场景演示二
蛙蛙被困在一个 3 × 3 的迷宫中，迷宫的左上角是起点，右下角是迷宫出口（用 exit 表示）。
迷宫中有些格子是 0，表示不可通行（可能是沼泽或岩石），其他格子是 1，表示可以安全落脚。
蛙蛙每次只能向上、右、下、左四个方向移动一格，且不能重复走过任何格子。由于蛙蛙体力有限，他希望尽快走出迷宫，请你告诉蛙蛙最少需要走多少步。迷宫中 (1, 3) 处为障碍物，(3, 3) 为终点，如表 9-6 所示。
表 9-6 蛙蛙所在的迷宫
| 蛙蛙 | 1 | 0 |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 1 | exit |
我们可以按照这样的思路去找。
- 从起点 (1, 1) 出发按照上、右、下、左四个方向的顺序进行遍历，先检查第 1 步可以到达的所有点，判断是否为终点，如表 9-7 所示。
表 9-7 第 1 步能到达 (1, 2) 和 (2, 1)
| 蛙蛙 | 1 | 障碍 |
|---|---|---|
| 1 | ||
- 依次从第 1 步到达的点出发，检查第 2 步可以到达的点是否为终点，如表 9-8 所示。
表 9-8 第 2 步能到达 (2, 2) 和 (3, 1)
| 蛙蛙 | 1 | 障碍 |
|---|---|---|
| 1 | 2 | |
| 2 |
- 依次从第 2 步到达的点出发，检查第 3 步可以到达的点是否为终点，如表 9-9 所示。
表 9-9 第 3 步能到达 (2, 3) 和 (3, 2)
| 蛙蛙 | 1 | 障碍 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 |
- 其中 (2, 3) 这个点比 (3, 2) 先遍历。先从 (2, 3) 出发，上方是障碍物不能走，右方出地图不能走，可以向下走来到 (3, 3)，此时共移动 4 步。检查到达的点是否为终点，如表 9-10 所示。
表 9-10 第 4 步到达终点 (3, 3)
| 蛙蛙 | 1 | 障碍 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
- 找到终点，程序结束，最先到达的点为最短路径，步数为 4。
问题建模
如何表示迷宫地图等信息呢？
使用一个 3 × 3 的二维数组 maze 来存储迷宫信息，如果值为 0 表示不可走，1 表示可走；再使用一个 3 × 3 的二维数组 used 来标记是否走过，没走过为 0，走过的话为 1。
例：used[1][2] = 1，表示 maze[1][2] 已经走过。
遍历方向
我们可以用一个 4 行 2 列的二维数组 fx 保存能够一步到达的四个方向。为了方便描述，我们按顺时针方向，从上方进行保存，即上、右、下、左的顺序，比如：
int fx[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};假设当前坐标为 (2, 2)，向上移动就是：(2 + fx[0][0], 2 + fx[0][1])，即来到坐标 (2 + (−1), 2 + 0) = (1, 2) 的位置。
注：建模与遍历均与深度优先搜索一致，详情请参考 9.2.1 节"问题建模"和"遍历方向"部分。
搜索过程
- 我们需要使用队列（这里用数组 que 模拟队列，如表 9-11 所示。队列的知识在 10.2 节中有详细讲解，若学习本节内容时对这方面有疑惑，可以跳到 10.2 节学完队列知识后再回来复习广度优先搜索）来实现，用结构体表示每次找到的点的坐标信息以及步数 (x, y, cnt)。
表 9-11 队列 que
| x | y | cnt |
|---|---|---|
- 将起点 (1, 1) 放入队列中（后面简称入队），如表 9-12 所示，并记录当前步数。由于在起点，蛙蛙还没开始走，所以步数为 0。
表 9-12 将起点 (1, 1) 放入队列 que 中
| x | y | cnt |
|---|---|---|
| 1 | 1 | 0 |
- 从队头元素（即从 maze 数组中的第 1 行第 1 列）出发，按上、右、下、左的顺序遍历它的四个方向（如表 9-13 所示），如果能到达则将其放入队列中，并且步数从队头的步数那里加 1。
表 9-13 在 maze 数组中开始遍历
| 蛙蛙 | 1 | 障碍 |
|---|---|---|
| 1 | ||
如表 9-13 所示，从 (1, 1) 可以走到的点是 (1, 2) 和 (2, 1)，所以需要让这两个点入队，且步数加 1（原步数为 0，现到达的这两个点的步数为 1），如表 9-14 所示。
表 9-14 让 (1, 2) 和 (2, 1) 入队
| x | y | cnt |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 2 | 1 |
| 2 | 1 | 1 |
由于 (1, 1) 这个点已经走过了，所以需要将它移出队列（如表 9-15 所示），下一次从 (1, 2) 这个点出发，可通过一个指针 head 实现这个操作，一开始 head 指向 (1, 1)，走过后将 head 指向下一个元素（这里用颜色标记，表示已经不在队列中）。
表 9-15 将已走过的 (1, 1) 移出队列
| x | y | cnt |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 2 | 1 |
| 2 | 1 | 1 |
- 判断是否到达终点，若到达终点则终止程序（如表 9-16 所示）。
表 9-16 判断是否到达终点
| 蛙蛙 | 1 | 障碍 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 |
在表 9-16 中，若从 (2, 3) 向下出发，则来到终点，步数加 1 为 4，此时程序结束，返回步数 4，即为最快到达的点（如表 9-17 所示）。
表 9-17 到达终点
| 蛙蛙 | 1 | 障碍 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
- 若没有到达终点，继续重复步骤 3)，直到找到终点或者队列中没有元素，若队列中没有元素则说明不能走到终点。
完整代码及解析
#include <iostream>
using namespace std;
// 定义一个结构体 wz 来表示位置信息
struct wz
{
int x, y; // 坐标，x 表示横坐标，y 表示纵坐标
int cnt; // 步数
} que[1000], front, a; // front 用来存储每次取出的队头元素，a 存储起点信息
int maze[5][5];
int used[5][5];
// fx 数组存储四个方向的偏移量，分别为上、右、下、左
int fx[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
// head 表示队列的队头位置，tail 表示队列的队尾位置
// sx, sy 分别表示起点的横坐标和纵坐标，ex, ey 分别表示终点的横坐标和纵坐标
int head = 1, tail = 1, sx = 1, sy = 1, ex = 3, ey = 3;
// 声明广度优先搜索函数 bfs
void bfs(wz a);
int main()
{
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
cin >> maze[i][j];
// 初始化起点信息，将起点的坐标和步数（初始为 0）赋值给结构体 a
a.x = sx, a.y = sy, a.cnt = 0;
bfs(a);
// 输出到达终点时所走的步数
cout << que[tail].cnt;
return 0;
}
// 广度优先搜索
void bfs(wz a)
{
// 将起点信息存入队列的队头位置
que[head] = a;
// 标记起点已经被访问过
used[a.x][a.y] = 1;
// 当队列不为空时，继续进行搜索
while (head <= tail)
{
// 取出队头元素
front = que[head];
// 队头指针后移，相当于队头元素出队
head++;
// 遍历队头元素的四个方向
for (int i = 0; i < 4; i++)
{
// 计算下一次前进点的坐标
int nx = front.x + fx[i][0], ny = front.y + fx[i][1];
// 检查下一个点是否满足条件：在地图内、未被访问过且不是障碍
if (nx >= 1 && nx <= 4 && ny >= 1 && ny <= 4 && !used[nx][ny] && maze[nx][ny])
{
// 队尾指针后移
tail++;
// 标记该点已经被访问过
used[nx][ny] = 1;
// 将该点的坐标和步数信息存入队列
que[tail].x = nx;
que[tail].y = ny;
// 该点的步数为前一个点的步数加 1
que[tail].cnt = front.cnt + 1;
}
// 如果到达终点
if (nx == ex && ny == ey)
{
// 让队头指针大于队尾指针，退出 while 循环
head = tail + 1;
// 退出 for 循环
break;
}
}
}
}运行后输入：
1 1 0
1 1 1
1 1 1运行结果：
441.2 广度优先搜索模板
上面走迷宫就是广度优先搜索的过程：从初始状态出发，到 1 次转移（1 步）能够到达的所有状态，再到 2 次转移（2 步）能够到达的所有状态……一直到 n 次转移能到达的所有状态。
我们常用广度优先搜索处理两种问题：
最短路径问题；
是否有路线的问题。
模板
void bfs(State a)
{
队头指针 head = 1, 队尾指针 tail = 1;
起始状态 a 入队;
while (head <= tail)
{
取出队头元素 State = que[head];
队头指针后移 head++;
// 尝试从队头元素出发可以得到的 n 个状态
for (int i = 1; i <= n; i++)
{
if (满足条件)
{
队尾后移，tail++
状态入队，并标记
}
if (到达终点)
{
退出 for 和 while 循环
}
}
}
}41.3 实例讲解
例 1：探险救援
正在森林中探险的蛙蛙，突然收到了同伴的求救信号，信号显示森林中有同伴受伤了，蛙蛙需要尽快赶到伤者那里帮忙。
森林可以看作一个 m × n 的地图，其中 w 表示蛙蛙，p 表示伤者，森林中可以行走的地方用 * 表示，其他符号表示不可走。
蛙蛙每次只能向上、下、左、右四个方向移动一步，请你告诉蛙蛙，他最少需要走几步。
【输入格式】输入 m + 1 行。
第 1 行输入 m 和 n，分别表示地图的行数和列数（1 ≤ m ≤ 40，1 ≤ n ≤ 40）。
第 2 行开始输入 m 行 n 列的地图内容，其中 w 表示蛙蛙的位置，p 表示伤者的位置，* 表示可以行走的地方，其他符号均表示不可行走。
【输出格式】输出一行。如果蛙蛙能走到伤者的位置，输出其最少步数，如果蛙蛙走不到伤者的位置，输出 No。
【输入样例】
4 4
w * * *
* * * *
* & * *
* * p *注：原书输入样例跨页排版错乱（地图第 2 行缺失、"p" 所在行错位到输出样例之后），此处已按 4 × 4 地图与输出结果 5 复原。
【输出样例】
5解析
利用广度优先搜索算法，蛙蛙从初始位置开始，按照步数最少的原则逐步探索地图，直到找到伤者或确定无法到达伤者的位置。如果找到了伤者，输出最少步数；如果无法到达伤者的位置，输出 No。
首先，从输入中读取地图的大小 m 和 n，以及地图的内容。当读到蛙蛙的位置 w 时，将其坐标 x、y 和步数 cnt（初始为 0）记录在结构体中。
队列：使用一个队列 que 来存储待探索的位置，队列中的每个元素是一个结构体 wz，包含位置的坐标 x 和 y，以及从起点到该位置的步数 cnt。
搜索过程
a. 将蛙蛙的初始位置 a 加入队列。
b. 当队列不为空时，取出队头元素 front。
c. 尝试向四个方向（上、右、下、左）移动一步，计算新位置 (nx, ny)。
d. 如果新位置未被访问过（used[nx][ny] == 0）且是可通行的（maze[nx][ny] == '*'）或为伤者的位置（maze[nx][ny] == 'p'），则将新位置加入队列，并将其步数设置为当前位置的步数加 1。
e. 如果新位置是伤者的位置（maze[nx][ny] == 'p'），则设置标志 flag = 1，并跳出循环，表示找到了伤者。
f. 输出结果：如果找到了伤者（flag == 1），则输出到伤者位置的步数 que[tail].cnt。
g. 如果在搜索过程中，队列为空（head > tail）且没有找到伤者（flag == 0），说明从蛙蛙的初始位置无法到达伤者的位置，此时输出 No。
参考代码
#include <iostream>
using namespace std;
// 定义一个结构体 wz 用于存储位置信息和步数
struct wz
{
int x, y; // 位置的横坐标和纵坐标
int cnt; // 从起点到该位置的步数
} que[1000], front, a;
char maze[40][40]; // 存储地图信息
// 定义四个方向的偏移量，分别为上、右、下、左
int fx[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int used[40][40];
// head 和 tail 用于队列操作，flag 标记是否找到伤者
int head = 1, tail = 1, m, n, flag = 0;
// 广度优先搜索函数
void bfs(wz a);
int main()
{
cin >> m >> n; // 输入地图的行数和列数
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> maze[i][j]; // 输入地图的每个位置信息
if (maze[i][j] == 'w')
{
// 找到蛙蛙的初始位置
a.x = i;
a.y = j;
a.cnt = 0; // 初始步数为 0
}
}
}
bfs(a); // 从蛙蛙的初始位置开始进行广度优先搜索
if (flag)
cout << que[tail].cnt; // 如果找到伤者，输出最少步数
else
cout << "No"; // 如果未找到伤者，输出 No
return 0;
}
// 广度优先搜索函数的实现
void bfs(wz a)
{
que[head] = a; // 将蛙蛙的初始位置加入队列
while (head <= tail) // 当队列不为空时，继续搜索
{
front = que[head]; // 取出队头元素
head++; // 队头指针后移
// 尝试向四个方向进行探索
for (int i = 0; i < 4; i++)
{
// 计算新的位置坐标
int nx = front.x + fx[i][0];
int ny = front.y + fx[i][1];
// 判断新位置是否满足条件：未被访问过，且是可通行的位置或伤者的位置
if (!used[nx][ny] && (maze[nx][ny] == '*' || maze[nx][ny] == 'p'))
{
tail++; // 队尾指针后移
used[nx][ny] = 1; // 标记新位置为已访问
// 将新位置加入队列
que[tail].x = nx;
que[tail].y = ny;
// 新位置的步数为当前位置的步数加 1
que[tail].cnt = front.cnt + 1;
}
// 如果新位置是伤者的位置
if (maze[nx][ny] == 'p')
{
flag = 1; // 标记已经找到伤者
head = tail + 1; // 清空队列，结束搜索
break; // 跳出循环
}
}
}
}例 2：闭合圈填充
在一个由数字 0 和 1 组成的 n × n 方阵中，存在一个任意形状的闭合圈，这个闭合圈外围完全由数字 1 构成，并且在形成闭合圈的过程中，只在上、下、左、右这四个方向上移动。
现在蛙蛙的任务是，将这个闭合圈内部的所有空白空间（即原本为 0 的区域）都填写成数字 2。
【输入格式】输入 n + 1 行。
第 1 行为一个整数 n（1 ≤ n ≤ 30）。
接下来 n 行，是由 0 和 1 组成的 n × n 的方阵，方阵内只有一个闭合圈，圈内至少有一个 0。
【输出格式】输出 n 行，为已经填好数字 2 的完整方阵。
【输入样例】
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1【输出样例】
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1注：原书输出样例跨页缺失最后两行，此处已按输入样例与算法规则补全。
解析
通过广度优先搜索算法找到闭合圈外部的 0 并标记，然后遍历方阵输出最终结果，将闭合圈内部的 0 替换为 2。
确定边界外的点：为了区分闭合圈内部和外部，我们可以从方阵边界外的点［例如 (0, 0) 点，它肯定在闭合圈外部］开始进行搜索。使用广度优先搜索算法，从这个起始点开始向上、右、下、左四个方向扩展，标记所有能到达的 0 点。这些被标记的 0 点就是在闭合圈外部的点。
标记外部的 0 点：在搜索过程中，将遇到的 0 点标记为一个特定的值（例如 −1），表示这些点已经被访问过且在闭合圈外部。
区分内部和外部：遍历整个方阵，根据每个点的值进行判断，如果点的值为 1，则它是闭合圈的一部分；如果点的值为 −1，则它在闭合圈外部，应该保持为 0；如果点的值为 0，则它在闭合圈内部，需要将其替换为 2。
输出结果：按照上述规则遍历完方阵后，输出最终修改后的方阵。
参考代码
#include <iostream>
using namespace std;
int a[32][32];
int fx[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
struct zb
{
int x, y;
} que[10000];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
int h = 1, e = 1;
// 将起始点 (0, 0)入队，它肯定在闭合圈外部
que[h].x = 0, que[h].y = 0;
// 开始广度优先搜索，只要队列不为空就持续搜索
while (h <= e)
{
for (int i = 0; i < 4; i++)
{
int nx = que[h].x + fx[i][0], ny = que[h].y + fx[i][1];
if (a[nx][ny] == 0 && nx >= 0 && nx <= n + 1 && ny >= 0 && ny <= n + 1)
{
e++;
a[nx][ny] = -1;
// 让新坐标入队，以便后面继续从该点向四周扩展
que[e].x = nx, que[e].y = ny;
}
}
h++;
}
// 遍历方阵，根据标记情况输出结果
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
// 如果该位置标记为-1，说明在闭合圈外部，输出 0
if (a[i][j] == -1)
cout << 0 << ' ';
// 如果该位置为 1，说明是闭合圈的边界，输出 1
else if (a[i][j] == 1)
cout << 1 << ' ';
// 其他情况，说明在闭合圈内部，输出 2
else
cout << 2 << ' ';
}
cout << endl;
}
return 0;
}