← 目录 / 算法文档 · 模块十一 搜索基础 / 11.1 BFS 广度优先搜索

11.1　BFS 广度优先搜索

层层向外扩展，像水波一样——BFS 能在无权图中找到最短路径。

本页目录
① BFS 是什么

BFS（Breadth-First Search，广度优先搜索）解决的是这类问题：从一个起点出发，走到终点最少需要几步？

它的策略很直接——先把离起点近的地方全部走到，再去走远一点的。就像往平静的湖面扔一块石头，水波总是一圈一圈地向外扩散，不会跳过近处直接去远处。

BFS 用队列来实现这个"按距离顺序访问"的过程。队列的特点是先进先出，保证了距离近的节点总是先被处理。

💡
为什么 BFS 能保证找到最短路？
BFS 第一次到达某个格子时，走的步数一定是最少的。因为 BFS 按距离从小到大的顺序访问——如果存在一条更短的路，那个格子早就已经被更少步数访问过了，不会等到现在才第一次到达。
② 模板代码

下面是 BFS 解迷宫最短路的完整代码。先整体看一遍，后面再逐行解释每一部分的作用。

C++ · BFS 迷宫最短路完整模板
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 105;
5int n, m;
6char grid[MAXN][MAXN]; // '.' 可走，'#' 障碍
7int dist[MAXN][MAXN]; // -1 表示未访问
8int dx[] = {0, 0, 1, -1}; // 四个方向：右、左、下、上
9int dy[] = {1, -1, 0, 0};
10
11int BFS(int sr, int sc, int er, int ec)
12{
13 memset(dist, -1, sizeof(dist));
14 queue<pair<int, int>> q;
15 dist[sr][sc] = 0;
16 q.push({sr, sc});
17
18 while (!q.empty())
19 {
20 auto [r, c] = q.front();
21 q.pop();
22
23 if (r == er && c == ec) return dist[er][ec];
24
25 for (int i = 0; i < 4; i++)
26 {
27 int nr = r + dx[i];
28 int nc = c + dy[i];
29 if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
30 if (grid[nr][nc] == '#' || dist[nr][nc] != -1) continue;
31 dist[nr][nc] = dist[r][c] + 1;
32 q.push({nr, nc});
33 }
34 }
35 return -1; // 走不到终点
36}
③ 代码逐行解析

代码分成三个部分，分别对应 BFS 的三个核心步骤：

三个核心步骤
第一步：初始化（对应代码第 13–16 行）
把所有格子的 dist 设为 -1，表示"还没去过"。然后把起点的距离设为 0 并放进队列。这是 BFS 的出发点。
第二步：循环取出队头（对应代码第 18–24 行）
只要队列不空，就取出最前面的格子。如果它就是终点，直接返回答案——因为 BFS 第一次到达某个格子时，步数一定是最少的。
第三步：扩展四个方向的邻居（对应代码第 25–33 行）
对当前格子的上下左右四个方向，跳过越界的、跳过障碍的、跳过已经去过的（dist != -1）。剩下的邻居：记录步数为当前步数 +1，放进队列。
⚠️
最容易写错的地方：标记"已访问"必须在入队时就做（第 31 行），而不是出队时。如果等到出队时才标记，同一个格子可能被放进队列很多次，程序变得非常慢。
④ 迷宫图解：BFS 如何找到最短路

下面用一个 5×5 的迷宫来直观地看 BFS 的扩展过程。格子里的数字是 BFS 算出的"从起点 S 到这个格子最少需要几步"，颜色越深表示距离越近。

迷宫里有两条路能从 S 走到 E：蓝色虚线是最短路（8步），橙色虚线是另一条更长的路（10步）。BFS 因为按步数从小到大扩展，会自动找到蓝色那条。

1 2 3 4 1 3 5 5 4 6 7 6 7 8 7 8 9 S E × × × × × × 图例 起点 S（步数 0） 步数 1–4 步数 5–7 步数 8–9 终点 E 障碍（不可通行） 最短路（8 步） 备选路（10 步） 格内数字 = BFS 步数 最短路径 8 步
格内数字是 BFS 计算出的到起点 S 的最短步数，颜色越深越近。蓝色虚线是 BFS 找到的最短路（8 步）；橙色虚线是另一条绕行路（10 步）。BFS 按层扩展，第一次到达 E 时一定走的是最短路。
⑤ 队列的变化过程

用坐标 (行, 列) 表示格子，追踪队列里的内容，看看 BFS 是怎么一步一步扩展的。

颜色说明：紫色 = 当前从队列取出处理，蓝色 = 等待在队列中，绿色 = 已处理完毕，红色 = 被跳过（障碍或已访问）。

BFS 队列状态变化（起点 S = (0,0)）
初始化
(0,0)
起点入队，dist[0][0]=0
取出 (0,0)
步数=0
(1,0)
(0,1)
上方和左方越界跳过；下方 (1,0) 和右方 (0,1) 入队，步数=1
取出 (1,0)
步数=1
(0,1)
(0,0) 已访问跳过；(2,0) 是障碍跳过；(1,1) 是障碍跳过。(0,1) 已在队中
取出 (0,1)
步数=1
(0,2)
(0,0) 已访问；(1,1) 障碍；(0,2) 入队，步数=2
取出 (0,2)
步数=2
(1,2)
(0,3)
(0,1) 已访问；(1,2) 和 (0,3) 入队，步数=3
继续扩展…
(1,2)
(0,3)
(2,2)
(0,4)
…
层层向外，步数依次增加，直到第一次取出 (4,4) 时返回答案 8
⑥ 在图上的 BFS

迷宫其实是图的一种特殊形式（每个格子是节点，相邻格子之间有边）。对于一般的图，BFS 的代码结构完全相同，只需要把"四个方向的邻居"换成"邻接表里的相邻节点"就行了：

C++ · 一般图的 BFS（邻接表）
1vector<int> adj[MAXN]; // adj[u] 存 u 的所有邻居
2int dist[MAXN];
3
4void BFS(int start)
5{
6 memset(dist, -1, sizeof(dist));
7 queue<int> q;
8 dist[start] = 0;
9 q.push(start);
10 while (!q.empty())
11 {
12 int u = q.front(); q.pop();
13 for (int v : adj[u]) // 遍历 u 的每个邻居 v
14 {
15 if (dist[v] != -1) continue; // 已访问，跳过
16 dist[v] = dist[u] + 1;
17 q.push(v);
18 }
19 }
20}
💡
对比迷宫版本和图版本，会发现它们几乎一模一样：迷宫版本多了越界检查和障碍检查，这是因为迷宫的"边"是隐含的（相邻格子之间有路），需要在代码里手动判断是否合法。
⑦ BFS vs DFS

BFS 和 DFS 都是搜索算法，选哪个取决于你要问的问题：

对比项BFS（广度优先）DFS（深度优先）
形象比喻 水波扩散，一圈一圈向外 走迷宫，一条路走到底再回头
用的数据结构 队列（先进先出） 栈 / 递归调用栈（先进后出）
能找最短路吗 ✅ 无权图中保证最短路 ❌ 不保证，可能走了弯路
内存占用 队列可能很大，O(n) 栈深度，O(路径长度)
适合解决 最少步数、最短距离、层次遍历 判断连通性、列举所有方案、回溯
记忆口诀 问"最少几步" → 用 BFS 问"能不能到/所有走法" → 用 DFS
📖
本节小结
・BFS 用队列保证"先近后远"的访问顺序，因此能找到无权图的最短路。
・关键点：入队时立刻标记已访问（设 dist），不能等到出队时再标记。
・迷宫 BFS：用 dx/dy 数组枚举四个方向，先判越界再判障碍。
・一般图 BFS：把"四个方向"换成"邻接表里的邻居"，其余结构完全相同。
・口诀：问最少几步用 BFS，问有没有路或所有方案用 DFS。