8 宽度优先搜索
GESP C++ 六级：宽度优先搜索（BFS）
核心目标：理解 BFS 的“逐层扩展”思想，掌握队列实现与访问标记，熟练在树、图、网格上应用 BFS 求最短路径、连通块、层序信息，掌握多源 BFS 与双向 BFS 的基本思路，能辨析 BFS 与 DFS 的适用场景。
BFS 就是“一层一层往外扩”；用队列实现，先入先出；第一次到达目标时就是最短路径（无权图）；树/图/网格是三大应用场景；多源 BFS 把所有起点一起入队，双向 BFS 从两端同时搜。
一、考纲定位
根据 CCF 官方考纲，GESP 六级明确要求掌握深度优先搜索（DFS） 和广度优先搜索（BFS） 的基本原理与实现，能够解决树、图、网格等结构上的搜索问题。
BFS 在六级考试中的考查分布：
| 考点 | 重要程度 | 典型考法 |
|---|---|---|
| BFS 基本思想与队列实现 | ★★★★★ | 选择题、代码填空 |
| 树上的 BFS（层序遍历） | 编程题、程序阅读 | |
| 图上的 BFS（无权图最短路） | 编程题 | |
| 网格上的 BFS（迷宫最短路） | 编程题高频 | |
| 多源 BFS | ★★★★☆ | 编程题 |
| 双向 BFS（了解） | ★★★☆☆ | 选择题 |
| BFS 与 DFS 的区别 | ★★★★★ | 选择题高频 |
二、BFS 基本概念
2.1 什么是 BFS
广度优先搜索（Breadth-First Search）是一种用于遍历或搜索树、图、网格等结构的算法。它的核心思想是：从起点开始，先访问所有距离为 1 的节点，再访问所有距离为 2 的节点，依此类推，像水波一样逐层向外扩散。
直观比喻：往平静的湖面扔一颗石子，波纹一圈一圈向外扩散，先到达近处，再到达远处。BFS 就是按“距离起点的层数”从小到大访问节点。
2.2 BFS 的核心要素
| 要素 | 作用 | 示例 |
|---|---|---|
| 队列 | 保证按层顺序访问 | queue<状态> q |
| 访问标记 | 防止重复入队 | visited[] 数组 |
| 层数/步数 | 记录当前扩展到第几层 | step 或 dist[] |
| 终止条件 | 找到目标或队列为空 | if (cur == target) return step |
2.3 BFS 与 DFS 的区别
| 对比项 | BFS | DFS |
|---|---|---|
| 数据结构 | 队列 | 栈 / 递归 |
| 遍历顺序 | 逐层扩展 | 一条路走到黑 |
| 最短路径 | ✅ 保证（无权图） | ❌ 不保证 |
| 空间复杂度 | O(宽度) | O(深度) |
| 适用场景 | 最短路径、层序、多源扩散 | 连通性、回溯、排列组合 |
三、BFS 通用模板
3.1 队列实现模板
void bfs(起点) {
queue<状态> q;
q.push(起点);
visited[起点] = true; // 入队时标记
while (!q.empty()) {
状态 cur = q.front();
q.pop();
if (cur == 目标) {
处理结果;
return;
}
for (所有可能的下一步) {
if (下一步合法 && !visited[下一步]) {
visited[下一步] = true; // 入队时标记，防止重复
q.push(下一步);
}
}
}
}
关键点：
- 入队时标记，不是出队时标记，否则同一节点可能被多次入队。
- 队列保证按层顺序，第一次到达目标时就是最短路径（无权图）。
- 如果只求可达性，可以不记录步数；如果求最短步数，需要记录层数。
3.2 记录步数的模板
struct Node {
int x, y, step;
};
int bfs(int sx, int sy, int ex, int ey) {
queue<Node> q;
q.push({sx, sy, 0});
visited[sx][sy] = true;
while (!q.empty()) {
Node cur = q.front(); q.pop();
if (cur.x == ex && cur.y == ey) {
return cur.step; // 第一次到达即最短
}
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (合法 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny, cur.step + 1});
}
}
}
return -1; // 无法到达
}
四、树上的 BFS
4.1 树的层序遍历
void levelOrder(TreeNode* root) {
if (!root) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* cur = q.front(); q.pop();
cout << cur->val << " ";
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}
4.2 按层输出
void levelOrderByLevel(TreeNode* root) {
if (!root) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int sz = q.size(); // 当前层的节点数
for (int i = 0; i < sz; i++) {
TreeNode* cur = q.front(); q.pop();
cout << cur->val << " ";
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
cout << endl; // 每层结束换行
}
}
4.3 求树的最小深度
int minDepth(TreeNode* root) {
if (!root) return 0;
queue<pair<TreeNode*, int>> q;
q.push({root, 1});
while (!q.empty()) {
auto [node, depth] = q.front(); q.pop();
if (!node->left && !node->right) return depth;
if (node->left) q.push({node->left, depth + 1});
if (node->right) q.push({node->right, depth + 1});
}
return 0;
}
五、图上的 BFS
5.1 无权图最短路径
int bfs(int start, int target, int n) {
vector<int> dist(n + 1, -1);
queue<int> q;
q.push(start);
dist[start] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
if (u == target) return dist[u];
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return -1;
}
5.2 连通分量个数
int countComponents(int n) {
vector<bool> visited(n + 1, false);
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
queue<int> q;
q.push(i);
visited[i] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
cnt++;
}
}
return cnt;
}
六、网格上的 BFS（迷宫最短路）
6.1 方向数组
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
6.2 迷宫最短步数
struct Node { int x, y, step; };
int bfs(int sx, int sy, int ex, int ey) {
queue<Node> q;
q.push({sx, sy, 0});
vis[sx][sy] = true;
while (!q.empty()) {
Node cur = q.front(); q.pop();
if (cur.x == ex && cur.y == ey) return cur.step;
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
!vis[nx][ny] && grid[nx][ny] != '#') {
vis[nx][ny] = true;
q.push({nx, ny, cur.step + 1});
}
}
}
return -1;
}
6.3 岛屿数量（BFS 版）
void bfs(int x, int y) {
queue<pair<int, int>> q;
q.push({x, y});
vis[x][y] = true;
while (!q.empty()) {
auto [cx, cy] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i], ny = cy + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
!vis[nx][ny] && grid[nx][ny] == '1') {
vis[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
七、多源 BFS
7.1 什么是多源 BFS
多源 BFS 是指有多个起点同时开始扩展的 BFS。将所有起点一起入队，然后正常进行 BFS，就能得到每个位置到“最近起点”的距离。
7.2 经典问题：腐烂的橘子
问题：网格中 0 表示空，1 表示新鲜橘子，2 表示腐烂橘子。每分钟腐烂橘子会感染上下左右的新鲜橘子，求所有橘子腐烂的最少分钟数。
int orangesRotting(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
queue<pair<int, int>> q;
int fresh = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (grid[i][j] == 2) q.push({i, j});
else if (grid[i][j] == 1) fresh++;
}
if (fresh == 0) return 0;
int minutes = 0;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
while (!q.empty()) {
int sz = q.size();
bool spread = false;
for (int k = 0; k < sz; k++) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1) {
grid[nx][ny] = 2;
q.push({nx, ny});
fresh--;
spread = true;
}
}
}
if (spread) minutes++;
}
return fresh == 0 ? minutes : -1;
}
关键点：所有腐烂橘子一开始都入队，逐层向外扩散，层数就是分钟数。
八、双向 BFS（了解）
8.1 核心思想
双向 BFS 从起点和终点同时开始 BFS，当两个搜索相遇时，就找到了最短路径。适合状态空间较大、但起点和终点都已知的场景。
8.2 基本框架
int biBFS(int start, int target) {
queue<int> q1, q2;
unordered_map<int, int> dist1, dist2;
q1.push(start); dist1[start] = 0;
q2.push(target); dist2[target] = 0;
while (!q1.empty() && !q2.empty()) {
// 扩展较小的一边
if (q1.size() > q2.size()) swap(q1, q2), swap(dist1, dist2);
int sz = q1.size();
for (int i = 0; i < sz; i++) {
int u = q1.front(); q1.pop();
for (int v : adj[u]) {
if (dist1.count(v)) continue;
dist1[v] = dist1[u] + 1;
if (dist2.count(v)) return dist1[v] + dist2[v];
q1.push(v);
}
}
}
return -1;
}
六级对双向 BFS 要求较低，了解思想即可。
九、GESP 六级 BFS 真题精讲
真题1：迷宫最短路径（编程题）
给定 n×m 的迷宫，
#是墙，.是路，求从 S 到 E 的最短步数。
#include <iostream>
#include <queue>
using namespace std;
struct Node { int x, y, step; };
int n, m;
char grid[105][105];
bool vis[105][105];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int main() {
cin >> n >> m;
int sx, sy, ex, ey;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
if (grid[i][j] == 'S') sx = i, sy = j;
if (grid[i][j] == 'E') ex = i, ey = j;
}
queue<Node> q;
q.push({sx, sy, 0});
vis[sx][sy] = true;
while (!q.empty()) {
Node cur = q.front(); q.pop();
if (cur.x == ex && cur.y == ey) {
cout << cur.step << endl;
return 0;
}
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i], ny = cur.y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
!vis[nx][ny] && grid[nx][ny] != '#') {
vis[nx][ny] = true;
q.push({nx, ny, cur.step + 1});
}
}
}
cout << -1 << endl;
return 0;
}
真题2：BFS 与 DFS 区别（选择题）
以下关于 BFS 和 DFS 的说法，正确的是（ ）。
A. BFS 用栈实现，DFS 用队列实现
B. BFS 适合求无权图最短路径，DFS 不保证最短路径
C. BFS 的空间复杂度是 O(深度)，DFS 是 O(宽度)
D. BFS 只能用于树，不能用于图
答案：B
真题3：多源 BFS（程序阅读）
以下代码实现了什么功能？
queue<pair<int,int>> q; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (grid[i][j] == 2) q.push({i, j}); while (!q.empty()) { ... }答案：多源 BFS，所有腐烂橘子同时向外扩散。
真题4：BFS 代码填空
下面 BFS 代码中，横线处应填入（ ）。
while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; ______; } } }答案：
q.push(v);
十、易错点汇总
- 入队时不标记，出队时才标记：导致同一节点多次入队，效率降低甚至死循环。
- 忘记判空就取队头：
q.front()前必须!q.empty()。 - 步数更新位置错误：步数在入队时更新为
cur.step + 1，不是出队时。 - 网格 BFS 忘记边界检查：
nx >= 0 && nx < n && ny >= 0 && ny < m不能漏。 - 多源 BFS 只入队一个起点：所有起点必须一起入队。
- BFS 求最短路用于带权图：BFS 只保证无权图最短路，带权图需要用 Dijkstra。
- 队列中存状态太大：可以只存坐标，步数用
dist数组记录。 - 层序遍历忘记记录当前层大小：按层输出时需要
int sz = q.size()。 - BFS 与 DFS 混淆：BFS 用队列，DFS 用栈/递归。
- 双向 BFS 交换队列时忘记交换距离数组：
swap(q1, q2), swap(dist1, dist2)。
十一、速查表
| 需求 | 写法 | 关键注意 |
|---|---|---|
| BFS 模板 | queue; push(起点); 标记; while (!empty) { pop; 遍历邻居; 标记+入队; } |
入队时标记 |
| 记录步数 | q.push({nx, ny, cur.step + 1}) |
入队时更新步数 |
| 树层序遍历 | queue<TreeNode*>; push(root); while { pop; 左右入队; } |
按层输出需 sz |
| 图最短路 | dist[] 数组 + 队列 |
无权图 |
| 网格 BFS | 方向数组 + 边界检查 | 入队时标记 |
| 多源 BFS | 所有起点一起入队 | 层数即扩散时间 |
| 双向 BFS | 两端同时 BFS，相遇即最短 | 扩展较小的一边 |
| BFS vs DFS | BFS 队列逐层，DFS 栈/递归深入 | BFS 保证无权最短路 |
十二、总结
宽度优先搜索是 GESP 六级搜索算法的核心内容。
- BFS 的核心是“逐层扩展”，用队列实现，先入先出。
- 入队时就要标记已访问，防止重复入队。
- BFS 第一次到达目标时就是最短路径（无权图）。
- 树上的 BFS 就是层序遍历，按层输出需记录当前层大小。
- 图上的 BFS 可求无权图最短路径和连通分量。
- 网格 BFS 用方向数组 + 边界检查，是迷宫最短路的标准解法。
- 多源 BFS 将所有起点一起入队，适合“腐烂橘子”类扩散问题。
- 双向 BFS 从起点和终点同时搜索，适合状态空间大的场景。
- BFS 不适用于带权图最短路，带权图要用 Dijkstra。
- 多练“迷宫最短路”“层序遍历”“多源 BFS”“连通分量”四类题。
复习建议：先把 BFS 通用模板和网格 BFS 模板写熟，确保闭卷能默写；再练习树上的层序遍历和按层输出；然后掌握多源 BFS 的入队方式；最后用真题做限时训练。考试中先判断题目考的是树、图还是网格，再确定用单源还是多源 BFS，最后检查标记、边界和步数更新。