📖 第 5.2 章
⏱️ 约 120 分钟
🎯 中级
第 5.2 章：BFS 与 DFS
📝 前置条件： 确保理解图的表示（第 5.1 章）、队列和栈（第 3.6 章）以及基本的二维数组遍历（第 2.3 章）。
图遍历算法探索从起点可到达的每个节点，是数十种图算法的基础。DFS（深度优先搜索）在回溯前尽量深入；BFS（广度优先搜索）逐层探索。知道何时用哪种是你在竞赛编程生涯中不断积累的技能。
5.2.1 深度优先搜索（DFS）
DFS 就像探索迷宫：一直向前走直到遇到死路，然后回溯尝试另一条路。它是最自然的图遍历——递归完成了大部分工作。
核心思想
想象你站在迷宫中的十字路口。DFS 说：选一条路，尽可能走到底。遇到死路（所有邻居都已访问），回溯到上一个十字路口，尝试下一条路。重复直到访问了所有可达节点。
这种「深入后回溯」的行为与递归完美对应：每次递归调用深入一步，从调用中返回就是回溯。
从节点 1 开始的 DFS：
1 ──── 2 ──── 4
| |
3 5 ──── 6
访问顺序：1 → 2 → 4（死路，回溯）→ 5 → 6（死路，回溯×2）→ 3
图示：DFS 遍历顺序
DFS 在回溯前尽量深入。带编号的圆圈展示访问顺序，红色虚线箭头展示回溯路径。右侧的调用栈说明了递归如何自然地实现 DFS 所需的 LIFO 行为。
递归 DFS
📄 查看代码：递归 DFS
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
vector<int> adj[MAXN];
bool visited[MAXN];
void dfs(int u) {
visited[u] = true; // 标记当前节点为已访问
cout << u << " "; // 处理 u（本例中打印它）
for (int v : adj[u]) { // 对每个邻居 v
if (!visited[v]) { // 若尚未访问
dfs(v); // 递归探索 v
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// 从节点 1 开始 DFS
dfs(1);
cout << "\n";
return 0;
}
逐步追踪：递归 DFS 如何工作
给定图（节点：1,2,3,4,5,6；边：1-2,1-3,2-4,2-5,5-6）：
📄 给定图（节点：1,2,3,4,5,6；边：1-2,1-3,2-4,2-5,5-6）：
DFS 从节点 1 开始——带调用栈的完整追踪：
调用：dfs(1)
visited[1] = true. 打印：1
节点 1 的邻居：[2, 3]
├── v=2：未访问 → 调用 dfs(2)
│ 调用：dfs(2)
│ visited[2] = true. 打印：2
│ 节点 2 的邻居：[1, 4, 5]
│ ├── v=1：已访问 → 跳过
│ ├── v=4：未访问 → 调用 dfs(4)
│ │ 调用：dfs(4)
│ │ visited[4] = true. 打印：4
│ │ 节点 4 的邻居：[2]
│ │ └── v=2：已访问 → 跳过
│ │ 从 dfs(4) 返回 ← 回溯！
│ ├── v=5：未访问 → 调用 dfs(5)
│ │ 调用：dfs(5)
│ │ visited[5] = true. 打印：5
│ │ 节点 5 的邻居：[2, 6]
│ │ ├── v=2：已访问 → 跳过
│ │ └── v=6：未访问 → 调用 dfs(6)
│ │ dfs(6)：打印 6
│ │ 从 dfs(6) 返回 ← 回溯！
│ │ 从 dfs(5) 返回 ← 回溯！
│ 从 dfs(2) 返回 ← 回溯！
├── v=3：未访问 → 调用 dfs(3)
│ dfs(3)：打印 3，无未访问邻居
│ 从 dfs(3) 返回 ← 回溯！
从 dfs(1) 返回
输出：1 2 4 5 6 3
💡 关键观察： 递归深度等于 DFS 树中从起始节点出发的最长路径。对于路径图 1→2→3→...→N，深度为 N——这就是栈溢出风险出现的时候。
重要： 始终在递归前而非之后标记节点为已访问！这能防止在环上无限循环。
复杂度分析
- 时间：
O(V + E)—— 每个顶点恰好访问一次（visited[]检查），每条边恰好检查两次（无向图中从两端各一次），总计 O(V + E)。 - 空间：
O(V)——visited[]数组使用 O(V)，递归调用栈最坏情况深度 O(V)。
迭代 DFS（使用栈）
对于非常大的图，递归 DFS 可能导致栈溢出（递归太深）。默认栈大小通常为 1–8 MB，每个递归层次使用约 100–200 字节。当图深度超过约 10^4–10^5 时会崩溃。
迭代版本用显式的 stack<int> 替换系统调用栈：
📄 迭代版本用显式的 `stack` 替换系统调用栈：
void dfs_iterative(int start, int n) {
vector<bool> visited(n + 1, false);
stack<int> st;
st.push(start);
while (!st.empty()) {
int u = st.top();
st.pop();
if (visited[u]) continue; // 可能被多次压入
visited[u] = true;
cout << u << " ";
for (int v : adj[u]) {
if (!visited[v]) {
st.push(v);
}
}
}
}
⚠️ 注意： 迭代 DFS 访问节点的顺序可能与递归 DFS 不同。对大多数题目这无所谓——两者都访问所有可达节点。
何时用迭代 DFS：
- 图深度可能超过约 10^4（如路径图、链）
- N×M ≥ 10^6 格子的网格问题
- 任何担心栈溢出的时候
5.2.2 连通分量
连通分量是顶点的最大集合，其中每个顶点都能通过边到达其他所有顶点。把它想象成连接节点的「岛屿」——从分量中任意节点开始 DFS，会访问同一分量中的所有其他节点，但不会访问外面的节点。
算法：用 DFS 给每个分量标记
策略很简单：
- 从 1 到 N 扫描所有节点
- 找到未访问节点时，这是一个新分量的起点
- 从该节点运行 DFS，给所有可达节点打上相同的分量 ID
- 重复直到所有节点都被标记
📄 4. 重复直到所有节点都被标记
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
vector<int> adj[MAXN];
int comp[MAXN]; // comp[v] = 顶点 v 的分量 ID（0 = 未访问）
void dfs(int u, int id) {
comp[u] = id;
for (int v : adj[u]) {
if (comp[v] == 0) { // 0 表示未访问
dfs(v, id);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int numComponents = 0;
for (int u = 1; u <= n; u++) {
if (comp[u] == 0) {
numComponents++;
dfs(u, numComponents); // 分配分量 ID
}
}
cout << "分量数量：" << numComponents << "\n";
// 打印各分量大小
vector<int> sz(numComponents + 1, 0);
for (int u = 1; u <= n; u++) sz[comp[u]]++;
for (int i = 1; i <= numComponents; i++) {
cout << "分量 " << i << "：" << sz[i] << " 个节点\n";
}
return 0;
}
常见 USACO 应用
连通分量以多种形式出现：
- 「有多少组？」 —— 统计分量数
- 「A 和 B 连通吗？」 —— 检查
comp[A] == comp[B] - 「最大组的大小？」 —— 找节点最多的分量
- 「加 K 条边能使图连通吗？」 —— 需要恰好
numComponents - 1条边
💡 替代方案：并查集（DSU） 也可以找连通分量，并支持动态添加边。我们将在第 5.5 章介绍 DSU。
5.2.3 广度优先搜索（BFS）
BFS 先探索所有距离为 1 的节点，再探索距离为 2 的，然后 3，以此类推。这使它非常适合在无权图中寻找最短路径。DFS 深入，BFS 扩张——就像池塘里的涟漪。
核心思想
BFS 使用队列（FIFO：先进先出）按距离源点的顺序处理节点：
- 从源节点（距离 0）开始
- 访问其所有邻居（距离 1）
- 访问其未访问的邻居（距离 2）
- 继续直到访问了所有可达节点
队列确保距离 d 的所有节点在距离 d+1 的任何节点之前被处理。这种逐层扩展保证了最短路径。
图示：BFS 逐层遍历
BFS 像池塘里的涟漪向外扩散。每「层」节点颜色不同，展示了距源点距离 d 的所有节点在距离 d+1 的任何节点之前被发现。底部的队列展示了处理顺序。
BFS 模板
以下 BFS 模板是本章最重要的代码模式，你会在数十道题中用到它（或它的变体）。
📄 以下 BFS 模板是本章**最重要的代码模式**，你会在数十道题中用到它（或它的变体）。
// BFS 最短路径 — O(V + E)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
vector<int> adj[MAXN];
// 返回从源点到所有顶点的最短距离数组
// dist[v] = -1 表示不可达
vector<int> bfs(int source, int n) {
vector<int> dist(n + 1, -1); // -1 = 未访问（也作为「已访问」标记）
queue<int> q;
dist[source] = 0; // 到源点的距离为 0
q.push(source); // 用源点初始化队列
while (!q.empty()) {
int u = q.front(); // 取出最早发现的节点
q.pop();
for (int v : adj[u]) { // 对 u 的每个邻居
if (dist[v] == -1) { // 若 v 尚未访问
dist[v] = dist[u] + 1; // ← 关键行：v 比 u 多一跳
q.push(v); // 将 v 加入队列以供未来处理
}
}
}
return dist;
}
关键部分逐行分析：
| 行 | 作用 | 为什么重要 |
|---|---|---|
dist(n+1, -1) | 将所有距离初始化为 -1 | -1 表示「尚未到达」——同时作为已访问标记 |
dist[source] = 0 | 源点到自身的距离为 0 | BFS 的起始点 |
q.push(source) | 初始化队列 | BFS 需要至少一个节点才能开始 |
u = q.front(); q.pop() | 处理最早发现的节点 | FIFO 顺序保证逐层处理 |
if (dist[v] == -1) | 只访问未访问的节点 | 防止重复访问和无限循环 |
dist[v] = dist[u] + 1 | 关键行 —— 距离加 1 | 无权图中每条边权重为 1 |
q.push(v) | 将 v 排队等待处理 | v 的邻居将在后续探索 |
BFS 为什么找到最短路径
BFS 按距离源点的顺序处理节点。第一次访问一个节点时，一定是通过最短路径。这是因为 BFS 在访问距离 d+1 的任何节点之前，会访问所有距离 d 的节点。
💡 核心思路： 把 BFS 想象成在水中投石——涟漪一层层向外扩散。距离 d 的所有单元格在距离 d+1 的任何单元格之前被处理。这种逐层处理保证了第一次到达任何节点都是通过最短路径。
BFS vs DFS 最短路径：
- BFS：保证无权图的最短路径 ✓
- DFS：不保证最短路径 ✗
5.2.4 网格 BFS——最常见的 USACO 模式
许多 USACO 题目给你一个有可通行（.）和阻塞（#）格子的网格。BFS 找从一个格子到另一个格子的最短路径。
图示：网格 BFS 距离洪水填充
从中心格子（距离 0）开始，BFS 扩展到所有可达格子，记录到达每个格子所需的最少步数。颜色越蓝表示越远。这正是 USACO 洪水填充和网格最短路径题目的工作方式。
USACO 风格的网格 BFS 题目：迷宫最短路
题目： 给定一个有墙（#）和开放格子（.）的 5×5 迷宫，找从左上角 (0,0) 到右下角 (4,4) 的最短路径。打印长度，若无路径输出 -1。
📄 C++ 完整代码
// 网格 BFS 最短路径 — O(R × C)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int R, C;
cin >> R >> C;
vector<string> grid(R);
for (int r = 0; r < R; r++) cin >> grid[r];
// 找起点 (S) 和终点 (E)，或使用固定角落
int sr = 0, sc = 0, er = R-1, ec = C-1;
// BFS 距离数组：-1 = 未访问
vector<vector<int>> dist(R, vector<int>(C, -1));
queue<pair<int,int>> q;
// 第一步：从源点初始化 BFS
dist[sr][sc] = 0;
q.push({sr, sc});
// 第二步：方向数组（上、下、左、右）
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
// 第三步：BFS 扩展
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr >= 0 && nr < R // 行在界内
&& nc >= 0 && nc < C // 列在界内
&& grid[nr][nc] != '#' // 不是墙
&& dist[nr][nc] == -1) { // ← 关键行：尚未访问
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
// 第四步：输出结果
if (dist[er][ec] == -1) {
cout << -1 << "\n"; // 无路径
} else {
cout << dist[er][ec] << "\n";
}
return 0;
}
⚠️ 常见错误： 在迷宫最短路中用 DFS 代替 BFS。DFS 可能找到一条路，但不是最短路。始终用 BFS 求无权网格的最短距离。
5.2.5 USACO 示例：洪水填充
USACO 喜欢「洪水填充」题目：找所有连通的同类型格子，或统计连通区域数。洪水填充本质上是网格上的 DFS/BFS——从种子格子开始「绘制」所有可达的同类型格子。
题目：统计连通区域
题目： 统计网格中「.」格子的不同连通区域数量。
. . # # .
. . # . .
# # # . .
. . . # #
. . . # .
「.」格子的区域：
区域 1： 区域 2： 区域 3：
. . . .
. . . . . .
. . . .
答案：3 个区域。
完整代码（带详细注释）
📄 查看代码：完整代码（带详细注释）
#include <bits/stdc++.h>
using namespace std;
int R, C;
vector<string> grid;
vector<vector<bool>> visited;
void floodFill(int r, int c) {
// 基础情况：越界时停止递归
if (r < 0 || r >= R || c < 0 || c >= C) return; // 越界
if (visited[r][c]) return; // 已访问
if (grid[r][c] == '#') return; // 墙（不是目标类型）
// 标记此格子为已访问（当前区域的一部分）
visited[r][c] = true;
// 向 4 个方向递归
floodFill(r - 1, c); // 上
floodFill(r + 1, c); // 下
floodFill(r, c - 1); // 左
floodFill(r, c + 1); // 右
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> R >> C;
grid.resize(R);
visited.assign(R, vector<bool>(C, false));
for (int r = 0; r < R; r++) cin >> grid[r];
int regions = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (!visited[r][c] && grid[r][c] == '.') {
regions++; // 找到新的未访问「.」格子 → 新区域！
floodFill(r, c); // 将此区域的所有格子标记为已访问
}
}
}
cout << regions << "\n";
return 0;
}
变体：BFS 洪水填充（避免栈溢出）
对于大网格（R × C ≥ 10^6），递归洪水填充可能栈溢出。改用 BFS：
📄 对于大网格（R × C ≥ 10^6），递归洪水填充可能栈溢出。改用 BFS：
void floodFillBFS(int sr, int sc) {
queue<pair<int,int>> q;
visited[sr][sc] = true;
q.push({sr, sc});
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < R && nc >= 0 && nc < C
&& !visited[nr][nc] && grid[nr][nc] == '.') {
visited[nr][nc] = true;
q.push({nr, nc});
}
}
}
}
💡 USACO 技巧： 洪水填充在 Bronze 和 Silver 级别非常常见。常见变体包括：统计区域数、找最大区域、检查两个格子是否在同一区域以及计算区域的周长。
5.2.6 多源 BFS
有时需要计算每个格子到最近特殊格子的距离——例如「每个空格子到最近火焰有多远？」从每个火焰格子分别启动 BFS 是 O(K × R × C)（K 是火焰数量）——太慢了。多源 BFS 一次 O(R × C) 的遍历就能解决。
核心思想
不是从一个源点运行 BFS，而是在开始 BFS 之前将所有源点格子压入队列，距离为 0。然后正常运行 BFS。每个格子都被分配到其最近源点的距离——由 BFS 的逐层性质保证。
为什么有效？ 想象一个虚拟「超级源点」S* 通过代价为 0 的边连接到所有真实源点。从 S* 做 BFS 会先访问所有真实源点（距离 0），然后是其邻居（距离 1），以此类推。多源 BFS 正是如此——不需要真正创建虚拟节点。
代码模板
📄 查看代码：代码模板
// 多源 BFS：同时从所有火焰格子出发
queue<pair<int,int>> q;
vector<vector<int>> dist(R, vector<int>(C, -1));
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
// 第一步：在开始 BFS 之前将所有源点以距离 0 压入队列
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r][c] == 'F') { // 火焰格子 = 源点
dist[r][c] = 0;
q.push({r, c});
}
}
}
// 第二步：从所有源点同时运行 BFS
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < R && nc >= 0 && nc < C
&& grid[nr][nc] != '#' && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
// BFS 后：dist[r][c] = (r,c) 到最近火焰格子的最小距离
💡 核心思路： 队列中源点的顺序无关紧要。BFS 先处理所有距离 0 的格子，再处理距离 1 的格子，以此类推。每个格子保证被最近的源点首先到达。
5.2.7 DFS vs BFS——何时用哪种
这是图问题中最重要的决策之一。以下是综合指南：
快速参考表
| 任务 | 用 | 原因 |
|---|---|---|
| 最短路径（无权） | BFS ✓ | 逐层保证最短 |
| 连通性/连通分量 | 任意 | 两者都行；DFS 递归更简单 |
| 环检测（有向） | DFS ✓ | 三色方案追踪当前路径 |
| 环检测（无向） | 任意 | DFS 加父节点检查，或 DSU |
| 拓扑排序 | DFS ✓ | 后序给出逆拓扑顺序 |
| 洪水填充 | 任意（DFS 更简单） | DFS 递归简洁 |
| 二部图检查 | BFS 或 DFS | 用任意方法 2-染色 |
| 到所有节点的距离 | BFS ✓ | BFS 自然计算所有距离 |
| 树遍历（前/中/后序） | DFS ✓ | 递归自然映射到树结构 |
| 路径是否存在（是/否） | 任意 | 两者都找所有可达节点 |
| 最近源点（多源） | BFS ✓ | 多源 BFS 是标准做法 |
决策流程图
需要最短路径/最少步数吗？
├── 是 → 用 BFS（始终！）
└── 否 → 需要探索路径/检测回边吗？
├── 是 → 用 DFS（递归追踪当前路径）
└── 否 → 任意都行，DFS 代码通常更短
💡 核心思路： 需要「最少步数」时用 BFS。只需要访问所有节点或检查路径属性（环、拓扑顺序、子树性质）时用 DFS。
USACO 经验法则：
- Bronze/Silver 网格题： BFS 最短路，DFS 洪水填充
- Silver 图论题： BFS 求距离，DFS 求分量
- Gold： DFS 拓扑排序、环检测；BFS 多源距离
⚠️ 第 5.2 章常见错误
错误一：用 DFS 求最短路径
DFS 深入探索一条路径，不保证最少步数。无权图的最短路径始终用 BFS。
错误二：网格 BFS 忘记边界检查
nr >= 0 && nr < R && nc >= 0 && nc < C —— 缺少其中任意一个条件都会导致越界崩溃。
// ✅ 正确：先检查边界，再检查网格
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] != '#')
错误三：弹出时而非压入时标记已访问
如果弹出时才标记已访问，同一个节点可能被多次压入，导致 O(V²) 的时间而非 O(V+E)。
为什么会这样——场景： 考虑一个节点 X，它有三个邻居 A、B、C，且这三个邻居此时都已经在队列中（同一 BFS 层）。当我们依次把它们出队时，每一个都会查看 X 并问："X 被访问过了吗？"
// ❌ 错误：弹出时才标记 → 同一节点会被多次压入
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
if (visited[r][c]) continue; // 浪费：队列中已经有很多份了
visited[r][c] = true;
for (...) {
if (!visited[nr][nc]) {
q.push({nr, nc}); // 可能被多个邻居重复压入！
}
}
}
// ✅ 正确：压入时立即标记 → 每个节点恰好压入一次
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (...) {
if (dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1; // 立即标记
q.push({nr, nc}); // 恰好压入一次
}
}
}
错误版本的执行追踪（A、B、C 依次出队，X 是它们共同的邻居）：
| 步骤 | 出队 | visited[X]？ | 对 X 的操作 | 本步后队列 |
|---|---|---|---|---|
| 1 | A | false | 压入 X | [B, C, X] |
| 2 | B | 仍是 false！ | 再次压入 X | [C, X, X] |
| 3 | C | 仍是 false！ | 再次压入 X | [X, X, X] |
| 4 | X | false → 置为 true | — | [X, X] |
| 5 | X | true → 跳过 | — | [X] |
| 6 | X | true → 跳过 | — | [] |
X 被入队 3 次、出队 3 次；只有第 4 步真正处理了它，第 5、6 步都是无用功。
影响： 在 1000×1000 的网格上（每格约 4 个邻居），错误版本可能将 多达 4 倍 的条目压入队列（400 万而非 100 万）——导致 TLE 或 MLE。最坏情况下（V 个节点、E = O(V²) 边的稠密图），错误版本的队列操作达 O(V + E) = O(V²)；正确版本保证恰好 V 次压入。稀疏图（E = O(V)）下两者都是 O(V)，但错误版本常数更大。
错误四：递归 DFS 栈溢出
对 N×M = 10^6 的网格，递归 DFS 可能超出默认栈大小（通常 1–8 MB）。改用迭代 BFS 或带显式栈的迭代 DFS。
错误五：0-indexed vs 1-indexed 起点用错
确保从正确的格子开始 BFS。USACO 题目有时用 1-indexed 网格，有时 0-indexed。
本章总结
📌 核心要点
| 算法 | 数据结构 | 时间 | 空间 | 最适合 |
|---|---|---|---|---|
| DFS（递归） | 调用栈 | O(V+E) | O(V) | 连通性、环检测、树问题 |
| DFS（迭代） | 显式栈 | O(V+E) | O(V) | 同上，避免栈溢出 |
| BFS | 队列 | O(V+E) | O(V) | 最短路径、逐层遍历 |
| 多源 BFS | 队列（多源预填充） | O(V+E) | O(V) | 到最近源点的距离 |
| 三色 DFS | 颜色数组 | O(V+E) | O(V) | 有向图环检测 |
| 拓扑排序 | DFS/BFS（Kahn） | O(V+E) | O(V) | DAG 上的排序/DP |
❓ 常见问题
Q1：BFS 和 DFS 的时间复杂度都是 O(V+E)，为什么 BFS 能找最短路径而 DFS 不能？
A：关键在访问顺序。BFS 用队列保证「先处理距离 d 的节点，再处理距离 d+1 的节点」，所以第一次到达一个节点始终是通过最短路径。DFS 用栈（或递归），可能经过长路到达节点，错过更短的路。
Q2：什么时候递归 DFS 会栈溢出？怎么修复？
A：默认栈大小约 1-8 MB，每次递归层次约用 100-200 字节。图深度超过约 10^4–10^5 时可能溢出。解决方案：① 切换到迭代 DFS（显式栈）；② 编译时增加栈大小。
Q3：网格 BFS 中为什么用 dist == -1 表示未访问而不是 visited 数组？
A：用
dist[r][c] == -1一举两得：同时记录「访问了没」和「到达的距离」。少一个数组，代码更简洁。
Q4：DFS 拓扑排序和 Kahn's BFS 拓扑排序，什么时候用哪个？
A：DFS 拓扑排序代码更短（直接反转后序），但 Kahn's 更直观，能检测环（若最终排序长度 < N，有环）。竞赛中两者都常见，选用你更熟悉的。
🔗 与后续章节的联系
- 第 5.4 章（二叉树与树算法）：树遍历（前/后序）本质上就是 DFS；第 5.5 章（并查集）处理动态连通性
- 第 6.1–6.3 章（DP）：「DAG 上的 DP」需要先做拓扑排序，再按拓扑顺序计算 DP
- BFS 最短路径是 Dijkstra（Gold 级别）的简化版——Dijkstra 处理加权图，BFS 处理无权图
- 多源 BFS 在 USACO Silver 中极为常见，是必须掌握的核心技术
练习题
题目 5.2.1 — 岛屿计数 🟢 简单
题目： 给定 N×M 网格，每个格子是 .（水）或 #（陆地）。水平或垂直相邻的陆地格子属于同一岛屿。统计不同岛屿的总数。
样例输入 1：
4 5
.###.
.#.#.
.###.
.....
样例输出 1： 1（所有 # 格子相连——一个岛屿）
样例输入 2：
3 5
#.#.#
.....
#.#.#
样例输出 2： 6（六个孤立的陆地格子，各自是一个岛屿）
💡 提示
扫描每个格子。找到未访问的 # 格子时，岛屿数加一，运行 DFS/BFS 标记所有相连的 # 格子为已访问。
✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int R, C;
vector<string> grid;
vector<vector<bool>> visited;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
void dfs(int r, int c) {
if (r < 0 || r >= R || c < 0 || c >= C) return;
if (visited[r][c] || grid[r][c] == '.') return;
visited[r][c] = true;
for (int d = 0; d < 4; d++)
dfs(r + dr[d], c + dc[d]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> R >> C;
grid.resize(R);
visited.assign(R, vector<bool>(C, false));
for (int r = 0; r < R; r++) cin >> grid[r];
int islands = 0;
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (!visited[r][c] && grid[r][c] == '#') {
islands++;
dfs(r, c);
}
cout << islands << "\n";
return 0;
}
// 时间：O(N×M)，空间：O(N×M)
题目 5.2.2 — 迷宫最短路 🟢 简单
题目： 给定带 S（起点）、E（终点）、.（可通行）和 #（墙）的 N×M 迷宫，找从 S 到 E 的最少步数（只能上下左右移动）。若无路径输出 −1。
样例输入 1：
5 5
S...#
####.
....E
.####
.....
样例输出 1： 10
样例输入 2：
3 3
S#E
.#.
...
样例输出 2： -1
💡 提示
从 S 开始 BFS。BFS 第一次到达 E 时，dist[E] 就是最少步数。BFS 结束仍未到达 E 则输出 −1。
✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int R, C;
cin >> R >> C;
vector<string> grid(R);
for (int r = 0; r < R; r++) cin >> grid[r];
int sr, sc, er, ec;
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++) {
if (grid[r][c] == 'S') { sr = r; sc = c; }
if (grid[r][c] == 'E') { er = r; ec = c; }
}
vector<vector<int>> dist(R, vector<int>(C, -1));
queue<pair<int,int>> q;
dist[sr][sc] = 0;
q.push({sr, sc});
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < R && nc >= 0 && nc < C
&& grid[nr][nc] != '#' && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
cout << dist[er][ec] << "\n";
return 0;
}
// 时间：O(N×M)，空间：O(N×M)
题目 5.2.3 — 二部图检查 🟡 中等
题目： 若能将每个节点染成黑色或白色，且每条边都连接黑色节点和白色节点，则图是二部图。给定无向图，判断是否是二部图，打印 "BIPARTITE" 或 "NOT BIPARTITE"。
样例输入 1： 4 个节点，边：1-2, 2-3, 3-4, 4-1 → BIPARTITE（4-环：1,3 黑，2,4 白）
样例输入 2： 3 个节点，边：1-2, 2-3, 3-1 → NOT BIPARTITE（三角形——奇数环不是二部图）
💡 提示
BFS 加 2-染色。给源点染色 0，对每个未染色的邻居染反色（1 - 当前颜色）。若邻居已有与当前节点相同的颜色，图不是二部图。
✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> color(n + 1, -1);
bool bipartite = true;
for (int start = 1; start <= n && bipartite; start++) {
if (color[start] != -1) continue;
queue<int> q;
color[start] = 0;
q.push(start);
while (!q.empty() && bipartite) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (color[v] == -1) {
color[v] = 1 - color[u];
q.push(v);
} else if (color[v] == color[u]) {
bipartite = false;
}
}
}
}
cout << (bipartite ? "BIPARTITE" : "NOT BIPARTITE") << "\n";
return 0;
}
题目 5.2.4 — 多源 BFS：最近火焰 🟡 中等
题目： 给定有火焰格子 F、可通行空格 . 和墙 # 的 N×M 网格，对每个空格打印到最近火焰格子的最小距离。墙不可穿越。若空格无法到达任何火焰，打印 −1。
样例输入：
3 4
.F..
.#.F
....
样例输出：
1 0 1 1
2 # 1 0
3 2 2 1
💡 提示
多源 BFS：在开始 BFS 之前，将所有 F 格子以距离 0 压入队列。然后 BFS 自然地给每个格子分配到最近火源的最小距离。
✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int R, C;
cin >> R >> C;
vector<string> grid(R);
for (auto& row : grid) cin >> row;
vector<vector<int>> dist(R, vector<int>(C, -1));
queue<pair<int,int>> q;
// 关键：将所有火源以距离 0 压入
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (grid[r][c] == 'F') {
dist[r][c] = 0;
q.push({r, c});
}
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < R && nc >= 0 && nc < C
&& grid[nr][nc] != '#' && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r][c] == '#') cout << "# ";
else cout << dist[r][c] << " ";
}
cout << "\n";
}
return 0;
}
题目 5.2.5 — USACO 2016 February Bronze：牛奶桶 🔴 困难
题目： 有两个空桶，容量分别为 X 和 Y。可用操作：将任意一桶装满、倒空任意一桶、将一桶倒入另一桶（直到其中一个满或空）。找到任意一桶中恰好有 M 升的最少操作次数。
样例输入： 3 5 4 → 输出： 6
💡 提示
建模为状态 BFS：每个状态是一对 (a, b)，其中 a ∈ [0,X]、b ∈ [0,Y] 是当前数量。应用 6 种操作生成邻居状态。BFS 找从 (0,0) 到满足 a==M 或 b==M 的任意状态的最少操作。
✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int X, Y, M;
cin >> X >> Y >> M;
vector<vector<int>> dist(X + 1, vector<int>(Y + 1, -1));
queue<pair<int,int>> q;
dist[0][0] = 0;
q.push({0, 0});
while (!q.empty()) {
auto [a, b] = q.front(); q.pop();
// 生成所有 6 种可能操作
vector<pair<int,int>> next = {
{X, b}, // 装满桶 A
{a, Y}, // 装满桶 B
{0, b}, // 倒空桶 A
{a, 0}, // 倒空桶 B
{max(0, a+b-Y), min(Y, a+b)}, // 将 A 倒入 B
{min(X, a+b), max(0, a+b-X)} // 将 B 倒入 A
};
for (auto [na, nb] : next) {
if (dist[na][nb] == -1) {
dist[na][nb] = dist[a][b] + 1;
q.push({na, nb});
}
}
}
int ans = INT_MAX;
for (int a = 0; a <= X; a++)
if (dist[a][M] != -1) ans = min(ans, dist[a][M]);
for (int b = 0; b <= Y; b++)
if (dist[M][b] != -1) ans = min(ans, dist[M][b]);
cout << (ans == INT_MAX ? -1 : ans) << "\n";
return 0;
}
// 时间：O(X×Y × 6) = O(X×Y)，空间：O(X×Y)
5.2.8 DFS 环检测——白/灰/黑染色
有向图环检测：三色 DFS
对于有向图，使用三色方案追踪 DFS 过程中每个节点的状态：
- 白色（0）： 尚未访问
- 灰色（1）： 当前在 DFS 调用栈中——已开始处理但尚未完成
- 黑色（2）： 完全处理完——所有后代都已探索
核心思路： 当且仅当 DFS 遇到回边（当前节点到灰色节点的边）时，存在环。灰色节点在当前 DFS 路径上，所以指回它的边创建了环。
📄 C++ 完整代码
// 有向图环检测 — O(V+E)
vector<int> color; // 0=白, 1=灰, 2=黑
bool hasCycle = false;
void dfs(int u) {
color[u] = 1; // 标记为「处理中」（灰色）
for (int v : adj[u]) {
if (color[v] == 0) {
dfs(v); // 未访问：递归
} else if (color[v] == 1) {
hasCycle = true; // ← 回边：v 是 u 的祖先 → 有环！
}
// color[v] == 2：已完全处理，安全跳过
}
color[u] = 2; // 标记为「完成」（黑色）
}
无向图环检测（更简单！）
对于无向图，不需要三色。规则更简单：DFS 过程中，若遇到已访问的节点且不是当前节点的父节点，就有环。
📄 对于**无向图**，不需要三色。规则更简单：DFS 过程中，若遇到已访问的节点且**不是当前节点的父节点**，就有环。
// 无向图环检测 — O(V+E)
void dfs(int u, int parent) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) {
dfs(v, u); // v 的父节点是 u
} else if (v != parent) {
hasCycle = true; // 已访问且不是父节点 → 有环！
}
}
}
// 调用：dfs(1, -1); // 从节点 1 开始，无父节点（用 -1 作哨兵）
5.2.9 拓扑排序
拓扑排序对**有向无环图（DAG）**的节点排序，使对每条边 u → v，u 在排序中排在 v 之前。
方法一：基于 DFS 的拓扑排序
📄 查看代码：方法一：基于 DFS 的拓扑排序
// 拓扑排序（DFS）— O(V+E)
vector<int> topoOrder;
void dfs(int u) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) dfs(v);
}
topoOrder.push_back(u); // ← 所有子节点处理完后加入（后序）
}
// 使用：
for (int u = 1; u <= n; u++)
if (!visited[u]) dfs(u);
reverse(topoOrder.begin(), topoOrder.end()); // 逆后序 = 拓扑顺序
方法二：Kahn 算法（基于 BFS 的拓扑排序）
📄 查看代码：方法二：Kahn 算法（基于 BFS 的拓扑排序）
// Kahn 算法：先处理入度为 0 的节点 — O(V+E)
vector<int> inDeg(n + 1, 0);
for (int u = 1; u <= n; u++)
for (int v : adj[u])
inDeg[v]++;
queue<int> q;
for (int u = 1; u <= n; u++)
if (inDeg[u] == 0) q.push(u); // 从无前置条件的节点开始
vector<int> order;
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (int v : adj[u]) {
inDeg[v]--;
if (inDeg[v] == 0) q.push(v);
}
}
// 若 order.size() != n，有环（不是 DAG）
if ((int)order.size() != n) cout << "有环\n";
else for (int u : order) cout << u << " ";
💡 关键应用： 拓扑排序是 DAG 上 DP 的基础。若依赖关系图是 DAG，按拓扑顺序处理节点——每个节点的 DP 状态只依赖之前处理过的节点。
5.2.10 变种一：0-1 BFS（权重只有 0 和 1）
问题引入
普通 BFS 只能处理无权图（每步代价相同）。当图的边权只有 0 或 1 时，用 Dijkstra 太重（O(E log V)），普通 BFS 又不对——但我们有更简单的方案：0-1 BFS，仍然 O(V+E)。
核心思想
用双端队列（deque） 代替普通队列：
- 经过权重为 0 的边 → 新节点从队首插入（代价不增，优先处理）
- 经过权重为 1 的边 → 新节点从队尾插入（代价 +1）
这样队列始终保持「距离单调不减」，与 BFS 的层序性质等价。
普通 BFS 队列（所有边权=1）：
队首 [d=0, d=1, d=1, d=2, d=2] 队尾
0-1 BFS 双端队列（边权0从队首，边权1从队尾）：
队首 [d=0, d=0, d=1, d=1, d=2] 队尾
↑ 权重0的邻居插到前面
完整实现
📄 查看代码：完整实现
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
// 0-1 BFS — O(V+E)
// adj[u] = {v, w}，w 只有 0 或 1
vector<pii> adj[MAXN];
vector<int> bfs_01(int src, int n) {
vector<int> dist(n + 1, INT_MAX);
deque<int> dq;
dist[src] = 0;
dq.push_front(src);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0)
dq.push_front(v); // 代价不增，放队首
else
dq.push_back(v); // 代价 +1，放队尾
}
}
}
return dist;
}
典型应用场景
| 场景 | 0-1 BFS 怎么建模 |
|---|---|
| 网格中某些格子可以免费穿越 | 免费格子边权 = 0，普通格子 = 1 |
| 换一次道路方向不花费用 | 反向走 = 0，顺向 = 1 |
| 可以携带有限数量的道具 | 扩展状态，使用道具时边权 = 0 |
5.2.11 变种二：双向 BFS（Bidirectional BFS）
问题引入
普通 BFS 从起点向外扩展，当图很大时，搜索空间是 O(b^d)（b = 分支因子，d = 距离）。
若从起点和终点同时扩展，总搜索空间变为 O(2 × b^(d/2)) = O(b^(d/2))，指数级加速！
核心思路
维护两个 BFS 前沿（frontier）：
- 正向前沿：从起点向外扩展
- 反向前沿：从终点向外扩展
每次扩展较小的前沿（减少总节点数）。当某个节点同时出现在两个前沿中，找到了最短路径。
📄 每次扩展**较小的前沿**（减少总节点数）。当某个节点同时出现在两个前沿中，找到了最短路径。
#include <bits/stdc++.h>
using namespace std;
// 双向 BFS — 适用于无权无向图，O(b^(d/2)) 而非 O(b^d)
// 返回 src 到 dst 的最短路径长度，-1 表示不可达
int bidir_bfs(int src, int dst, int n, vector<vector<int>>& adj) {
if (src == dst) return 0;
// 两个方向的距离数组，-1 = 未访问
vector<int> dist_f(n + 1, -1), dist_b(n + 1, -1);
queue<int> qf, qb;
dist_f[src] = 0; qf.push(src);
dist_b[dst] = 0; qb.push(dst);
while (!qf.empty() || !qb.empty()) {
// 每次扩展较小的前沿
if (qf.size() <= qb.size()) {
// 扩展正向一层
int sz = qf.size();
while (sz--) {
int u = qf.front(); qf.pop();
for (int v : adj[u]) {
if (dist_f[v] == -1) {
dist_f[v] = dist_f[u] + 1;
qf.push(v);
}
// 若 v 已被反向 BFS 访问 → 找到！
if (dist_b[v] != -1)
return dist_f[v] + dist_b[v];
}
}
} else {
// 扩展反向一层
int sz = qb.size();
while (sz--) {
int u = qb.front(); qb.pop();
for (int v : adj[u]) {
if (dist_b[v] == -1) {
dist_b[v] = dist_b[u] + 1;
qb.push(v);
}
if (dist_f[v] != -1)
return dist_f[v] + dist_b[v];
}
}
}
}
return -1; // 不可达
}
速度对比
| 图类型 | BFS 节点数 | 双向 BFS 节点数 |
|---|---|---|
| 分支因子 b=10，距离 d=6 | 10^6 = 1,000,000 | 2 × 10^3 = 2,000 |
| 分支因子 b=4，距离 d=20 | 4^20 ≈ 10^12 | 2 × 4^10 ≈ 2×10^6 |
5.2.12 变种三：DFS 回溯与剪枝
什么是回溯？
回溯是 DFS 的一种应用模式：系统地枚举所有可能的选择，发现不合法时撤销（回溯）。
三要素：
- 选择：在当前状态下做一个决定
- 递归：进入下一层状态
- 撤销：从递归返回后，撤销这个决定（恢复现场）
模板框架
📄 查看代码：模板框架
void backtrack(状态) {
if (达到终止条件) {
记录结果;
return;
}
for (每个可能的选择) {
if (选择不合法) continue; // 剪枝：提前排除无效分支
做选择; // 修改状态
backtrack(新状态); // 递归
撤销选择; // 恢复状态（回溯！）
}
}
经典例题一：全排列
📄 查看代码：经典例题一：全排列
// 生成 [1..n] 的所有排列
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> result;
vector<int> perm;
vector<bool> used;
void backtrack(int n) {
if ((int)perm.size() == n) {
result.push_back(perm);
return;
}
for (int i = 1; i <= n; i++) {
if (used[i]) continue; // 剪枝：已使用过，跳过
used[i] = true;
perm.push_back(i); // 做选择
backtrack(n); // 递归
perm.pop_back(); // 撤销选择
used[i] = false;
}
}
int main() {
int n = 3;
used.assign(n + 1, false);
backtrack(n);
for (auto& p : result) {
for (int x : p) cout << x << " ";
cout << "\n";
}
// 输出全部 6 种排列：1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 1 2 / 3 2 1
return 0;
}
经典例题二：N 皇后
在 N×N 棋盘上放置 N 个皇后，使任意两个皇后不在同一行、列、对角线。
📄 在 N×N 棋盘上放置 N 个皇后，使任意两个皇后不在同一行、列、对角线。
#include <bits/stdc++.h>
using namespace std;
int n;
int ans = 0;
vector<int> col; // col[r] = 第 r 行皇后所在的列
bool is_valid(int row, int c) {
for (int r = 0; r < row; r++) {
if (col[r] == c) return false; // 同列
if (abs(col[r] - c) == abs(r - row)) return false; // 对角线
}
return true;
}
void solve(int row) {
if (row == n) { ans++; return; }
for (int c = 0; c < n; c++) {
if (!is_valid(row, c)) continue; // 剪枝
col[row] = c; // 做选择：第 row 行放在列 c
solve(row + 1); // 递归下一行
// 无需显式撤销：下次赋值会覆盖 col[row]
}
}
int main() {
cin >> n;
col.resize(n);
solve(0);
cout << ans << "\n"; // n=8 输出 92
return 0;
}
更快的 N 皇后（位运算剪枝）
📄 查看代码：更快的 N 皇后（位运算剪枝）
// 用位运算表示列/主对角线/副对角线的占用情况，O(n!) 但常数极小
int n, ans = 0;
void solve(int row, int cols, int diag1, int diag2) {
if (row == n) { ans++; return; }
// 所有被占用的位置的掩码
int occupied = cols | diag1 | diag2;
// 可以放置的列：取反后取低 n 位
int available = (~occupied) & ((1 << n) - 1);
while (available) {
int bit = available & (-available); // 取最低的可用位
available -= bit;
solve(row + 1,
cols | bit,
(diag1 | bit) << 1,
(diag2 | bit) >> 1);
}
}
int main() {
cin >> n;
solve(0, 0, 0, 0);
cout << ans << "\n";
}
5.2.13 变种四：割点与桥（Tarjan 算法）
问题引入
在一个通信网络中，哪个节点被摧毁会导致网络分裂？哪条线路被切断会导致网络不连通？
- 割点（Articulation Point）： 删除该节点后图的连通分量数增加
- 桥（Bridge）： 删除该边后图的连通分量数增加
核心思想：DFS 序 + low 值
DFS 时给每个节点分配一个时间戳 disc[u]（进入时间）。
再定义 low[u] = 通过 u 的子树（含至多一条回边）能到达的最早时间戳。
low[u] = min(
disc[u], // u 自身的时间戳
min(disc[v] for all v: (u,v) 是回边), // 直接回边
min(low[v] for all v: v 是 u 的树边子节点) // 子节点的 low 值
)
判断割点：
- 根节点：有 ≥ 2 个子树子节点
- 非根节点 u：存在子节点 v 使得
low[v] >= disc[u]（v 的子树无法绕过 u 连到 u 的祖先）
判断桥： 边 (u, v) 是桥当且仅当 low[v] > disc[u]（v 的子树严格不能绕过这条边）
📄 C++ 完整代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> adj[MAXN];
int disc[MAXN], low[MAXN], timer_val = 0;
bool visited[MAXN], is_cut[MAXN];
vector<pair<int,int>> bridges;
void dfs(int u, int parent) {
visited[u] = true;
disc[u] = low[u] = ++timer_val;
int child_cnt = 0; // u 作为根时的子树数量
for (int v : adj[u]) {
if (!visited[v]) {
child_cnt++;
dfs(v, u);
low[u] = min(low[u], low[v]);
// 判断割点（非根）
if (parent != -1 && low[v] >= disc[u])
is_cut[u] = true;
// 判断桥
if (low[v] > disc[u])
bridges.push_back({u, v});
} else if (v != parent) {
// 回边（不走父节点方向）
low[u] = min(low[u], disc[v]);
}
}
// 判断割点（根节点：有 >= 2 个子树）
if (parent == -1 && child_cnt >= 2)
is_cut[u] = true;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (!visited[i]) dfs(i, -1);
cout << "割点：";
for (int i = 1; i <= n; i++)
if (is_cut[i]) cout << i << " ";
cout << "\n桥：";
for (auto [u, v] : bridges)
cout << u << "-" << v << " ";
cout << "\n";
return 0;
}
完整追踪示例
📄 查看代码：完整追踪示例
图：1-2-3-4，另有 2-4
DFS 从 1 开始：disc[1]=1, low[1]=1
→ 访问 2：disc[2]=2, low[2]=2
→ 访问 3：disc[3]=3, low[3]=3
→ 访问 4：disc[4]=4, low[4]=4
→ 邻居 2 已访问（回边）：low[4] = min(4, disc[2]) = 2
回退到 3：low[3] = min(3, low[4]) = 2
回退到 2：low[2] = min(2, low[3]) = 2
low[3]=2 >= disc[2]=2? YES → 2 是割点（删2后3-4孤立）
注意：low[3]=2 不严格大于 disc[2]=2，所以 2-3 不是桥
最终：割点={2}，桥={}
5.2.14 变种五：迭代加深 DFS（IDDFS）
问题引入
如果你需要找最短路径，但图太大无法用 BFS（内存不足），或者需要找有限步数内的解，可以使用 迭代加深 DFS（Iterative Deepening DFS，IDDFS）。
特点：
- 用 DFS 的空间效率（O(d)，只记当前路径）
- 用 BFS 的最优性（逐层探索）
原理： 从深度限制 limit=1 开始，不断增加限制，每次做一次深度受限的 DFS：
limit=1 → DFS 最多走 1 步
limit=2 → DFS 最多走 2 步
limit=3 → DFS 最多走 3 步
...
直到找到目标
每次重新从根出发，看起来浪费，但由于树的节点数指数增长，最深一层的节点占大部分，总代价只比 BFS 多约 35%（当 b=2 时），却省去了 BFS 的大量内存。
📄 C++ 完整代码
#include <bits/stdc++.h>
using namespace std;
// 迭代加深 DFS 框架
bool dfs_limited(int node, int depth, int limit, int parent,
vector<vector<int>>& adj) {
if (depth == limit) {
// 在最大深度检查是否是目标
return is_goal(node);
}
for (int v : adj[node]) {
if (v == parent) continue;
if (dfs_limited(v, depth + 1, limit, node, adj))
return true;
}
return false;
}
int iddfs(int src, int max_depth, vector<vector<int>>& adj) {
for (int limit = 0; limit <= max_depth; limit++) {
if (dfs_limited(src, 0, limit, -1, adj))
return limit; // 找到目标，返回最小步数
}
return -1; // 未找到
}
A* 搜索简介
IDDFS 的升级版是 IDA*（Iterative Deepening A*）：在深度限制的基础上加入启发函数 h(n)（对剩余距离的估计），直接剪掉 depth + h(n) > limit 的分支。
📄 C++ 完整代码
// IDA* 框架
int threshold;
int target;
int h(int node) {
return /* 到目标的估计距离（必须是下界）*/;
}
int search(int node, int g, int parent, vector<vector<int>>& adj) {
int f = g + h(node);
if (f > threshold) return f; // 超过阈值，剪枝并返回 f
if (node == target) return -1; // 找到！-1 作为成功标志
int min_t = INT_MAX;
for (int v : adj[node]) {
if (v == parent) continue;
int t = search(v, g + 1, node, adj);
if (t == -1) return -1;
min_t = min(min_t, t);
}
return min_t;
}
int ida_star(int src) {
threshold = h(src);
while (true) {
int t = search(src, 0, -1, adj);
if (t == -1) return threshold; // 找到
if (t == INT_MAX) return -1; // 无解
threshold = t; // 更新阈值
}
}
5.2.15 变种六：BFS 分层遍历
二叉树的层序遍历
BFS 的一个重要变种是精确追踪当前在第几层（第几步），常用于树的层序遍历、按层输出节点等。
📄 BFS 的一个重要变种是**精确追踪当前在第几层**（第几步），常用于树的层序遍历、按层输出节点等。
// 层序遍历二叉树，每层单独输出
#include <bits/stdc++.h>
using namespace std;
struct TreeNode { int val; TreeNode* left, *right; };
vector<vector<int>> level_order(TreeNode* root) {
if (!root) return {};
vector<vector<int>> result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int sz = q.size(); // 当前层的节点数
vector<int> level;
for (int i = 0; i < sz; i++) {
TreeNode* node = q.front(); q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(level); // 一整层
}
return result;
}
图的 BFS 按层处理
在图中，有时需要「先处理完所有距离 d 的节点，再处理距离 d+1 的」。方法完全相同：用 sz = q.size() 快照当前层大小。
📄 C++ 完整代码
// 图 BFS 按层处理模板
void bfs_by_layer(int src, vector<vector<int>>& adj, int n) {
vector<int> dist(n + 1, -1);
queue<int> q;
dist[src] = 0;
q.push(src);
int layer = 0;
while (!q.empty()) {
int sz = q.size(); // 当前层的节点数量
cout << "第 " << layer << " 层：";
for (int i = 0; i < sz; i++) {
int u = q.front(); q.pop();
cout << u << " ";
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
cout << "\n";
layer++;
}
}
5.2.16 变种七：记忆化 DFS（DFS + 动态规划）
DFS 经常需要处理重叠子问题——相同状态被多次访问。用记忆化（memoization）避免重复计算，这正是 DP 的核心。
记忆化 DFS 模板
📄 查看代码：记忆化 DFS 模板
// 有向图上，从节点 u 出发能到达的最大价值（记忆化 DFS）
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> adj[MAXN];
int val[MAXN]; // 每个节点的价值
int memo[MAXN]; // memo[u] = 从 u 出发的最大价值（-1=未计算）
int dfs(int u) {
if (memo[u] != -1) return memo[u]; // 已算过，直接返回
memo[u] = val[u]; // 至少获得当前节点的价值
for (int v : adj[u]) {
memo[u] = max(memo[u], val[u] + dfs(v));
}
return memo[u];
}
int main() {
cin >> n;
fill(memo, memo + n + 1, -1);
// ... 读入图和价值 ...
int ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, dfs(i));
cout << ans << "\n";
return 0;
}
记忆化 DFS vs 标准 DP
| 对比 | 记忆化 DFS | 标准 DP（递推） |
|---|---|---|
| 编写方式 | 递归（自顶向下） | 迭代（自底向上） |
| 何时计算 | 用到时才算 | 按顺序全部算 |
| 适用场景 | 状态转移顺序复杂时 | 状态转移顺序清晰时 |
| 栈溢出风险 | 有（深度过大时） | 无 |
5.2.17 BFS/DFS 变种速查表
| 变种 | 场景 | 数据结构 | 时间复杂度 |
|---|---|---|---|
| 普通 BFS | 无权最短路、连通性 | 队列 | O(V+E) |
| 普通 DFS | 连通性、环检测、拓扑排序 | 栈/递归 | O(V+E) |
| 0-1 BFS | 边权 0 或 1 的最短路 | 双端队列 | O(V+E) |
| 双向 BFS | 大图中点对最短路 | 两个队列 | O(b^(d/2)) |
| 多源 BFS | 到多个源点的最短距离 | 队列（多源初始化） | O(V+E) |
| 回溯 DFS | 枚举所有合法方案 | 递归+恢复现场 | 问题相关 |
| 割点/桥 | 找关键节点/边 | DFS+disc/low | O(V+E) |
| IDDFS | 内存受限的最短路 | 递归（限深） | O(b^d)，空间 O(d) |
| BFS 分层 | 按层处理节点 | 队列+层快照 | O(V+E) |
| 记忆化 DFS | DAG 上 DP | 递归+备忘录 | O(状态数×转移数) |
变种专项练习题（共 8 道，全部含完整解答）
题目 5.2.6 — 0-1 BFS：网格最少翻转 🟡 中等
题目： N×M 网格，每格是 0（免费通过）或 1（需花费 1 元）。从左上角到右下角，求最少花费。
示例：
输入：3 3
0 1 0
0 0 1
1 0 0
输出：0
（路径 (0,0)→(1,0)→(1,1)→(2,1)→(2,2)，全走 0 格，花费 0）
✅ 完整解答
思路： 经过 0 格子边权为 0，经过 1 格子边权为 1，使用 0-1 BFS（双端队列）。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int R, C; cin >> R >> C;
vector<vector<int>> grid(R, vector<int>(C));
for (auto& row : grid) for (int& x : row) cin >> x;
vector<vector<int>> dist(R, vector<int>(C, INT_MAX));
deque<pair<int,int>> dq;
dist[0][0] = grid[0][0];
dq.push_back({0, 0});
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
while (!dq.empty()) {
auto [r, c] = dq.front(); dq.pop_front();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
int nd = dist[r][c] + grid[nr][nc];
if (nd < dist[nr][nc]) {
dist[nr][nc] = nd;
if (grid[nr][nc] == 0)
dq.push_front({nr, nc}); // 免费：队首
else
dq.push_back({nr, nc}); // 花费：队尾
}
}
}
cout << dist[R-1][C-1] << "\n";
return 0;
}
追踪：
dist[0][0]=0（grid=0，放队首）
处理(0,0)：扩展(1,0) grid=0→dist=0，放队首；(0,1) grid=1→dist=1，放队尾
处理(1,0)：扩展(1,1) grid=0→dist=0；(2,0) grid=1→dist=1
...
最终 dist[2][2] = 0
题目 5.2.7 — 回溯：子集枚举 🟢 简单
题目： 给定长度为 N 的数组，输出所有子集（包含空集），每行一个子集，元素从小到大，子集按字典序排列。
示例：
📄 Code 完整代码
输入：3
1 2 3
输出：
（空行，空集）
1
1 2
1 2 3
1 3
2
2 3
3
✅ 完整解答
思路： 对每个元素，递归时选择「选」或「不选」（二叉回溯树）。
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a, cur;
void backtrack(int idx) {
// 输出当前子集
for (int i = 0; i < (int)cur.size(); i++) {
if (i) cout << " ";
cout << cur[i];
}
cout << "\n";
for (int i = idx; i < n; i++) {
cur.push_back(a[i]); // 选 a[i]
backtrack(i + 1);
cur.pop_back(); // 不选 a[i]（回溯）
}
}
int main() {
cin >> n;
a.resize(n);
for (int& x : a) cin >> x;
sort(a.begin(), a.end()); // 保证字典序
backtrack(0);
return 0;
}
理解回溯树（N=2，a=[1,2]）：
backtrack(0)：输出[]
选1 → backtrack(1)：输出[1]
选2 → backtrack(2)：输出[1,2]
不选2
不选1
选2 → backtrack(2)：输出[2]
不选2
题目 5.2.8 — 回溯+剪枝：数字组合求和 🟡 中等
题目： 给定不含重复元素的正整数数组 candidates 和目标值 target，找出所有和为 target 的组合（每个数可以重复使用，组合内数字升序排列，不同组合间无重复）。
示例：
candidates=[2,3,6,7], target=7
输出：[2,2,3], [7]
✅ 完整解答
#include <bits/stdc++.h>
using namespace std;
vector<int> cands;
vector<vector<int>> result;
vector<int> cur;
void backtrack(int idx, int remain) {
if (remain == 0) {
result.push_back(cur);
return;
}
for (int i = idx; i < (int)cands.size(); i++) {
if (cands[i] > remain) break; // 剪枝：已排序，超过 remain 的后续都不用看
cur.push_back(cands[i]);
backtrack(i, remain - cands[i]); // i 而非 i+1，允许重复使用
cur.pop_back();
}
}
int main() {
int n, target;
cin >> n >> target;
cands.resize(n);
for (int& x : cands) cin >> x;
sort(cands.begin(), cands.end()); // 排序，为了剪枝和去重
backtrack(0, target);
for (auto& v : result) {
for (int i = 0; i < (int)v.size(); i++) {
if (i) cout << " ";
cout << v[i];
}
cout << "\n";
}
return 0;
}
关键剪枝： 数组已排序，若 cands[i] > remain，后续更大的数也一定超过，直接 break。
题目 5.2.9 — 双向 BFS：单词接龙 🟡 中等
题目： 给定起始单词 beginWord、目标单词 endWord 和单词列表。每次只能改变一个字母，且改变后的单词必须在列表中。求从 beginWord 到 endWord 的最短转换路径长度，若不存在返回 0。
示例：
beginWord = "hit", endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
输出：5（hit→hot→dot→dog→cog）
✅ 完整解答
普通 BFS 版：
#include <bits/stdc++.h>
using namespace std;
int word_ladder(string begin, string end, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(end)) return 0;
queue<string> q;
unordered_map<string, int> dist;
dist[begin] = 1;
q.push(begin);
while (!q.empty()) {
string cur = q.front(); q.pop();
// 枚举所有相差一个字母的单词
for (int i = 0; i < (int)cur.size(); i++) {
string next = cur;
for (char c = 'a'; c <= 'z'; c++) {
next[i] = c;
if (next == cur) continue;
if (next == end) return dist[cur] + 1;
if (words.count(next) && !dist.count(next)) {
dist[next] = dist[cur] + 1;
q.push(next);
}
}
}
}
return 0;
}
int main() {
string begin, end; int n;
cin >> begin >> end >> n;
vector<string> wordList(n);
for (auto& w : wordList) cin >> w;
cout << word_ladder(begin, end, wordList) << "\n";
return 0;
}
双向 BFS 优化版（大词表时更快）：
int word_ladder_bidir(string begin, string end, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(end)) return 0;
// 两个方向的已访问集合
unordered_set<string> front_visited = {begin};
unordered_set<string> back_visited = {end};
int step = 1;
while (!front_visited.empty() && !back_visited.empty()) {
// 每次扩展较小的前沿（提高效率）
if (front_visited.size() > back_visited.size())
swap(front_visited, back_visited);
unordered_set<string> next_front;
for (const string& word : front_visited) {
string next = word;
for (int i = 0; i < (int)next.size(); i++) {
char orig = next[i];
for (char c = 'a'; c <= 'z'; c++) {
next[i] = c;
if (back_visited.count(next)) return step + 1; // 相遇！
if (words.count(next) && !front_visited.count(next))
next_front.insert(next);
next[i] = orig;
}
}
}
front_visited = next_front;
step++;
}
return 0;
}
题目 5.2.10 — 割点与桥：关键服务器 🔴 困难
题目： 有 N 台服务器和 M 条连接。若断开某条连接后，某些服务器无法相互通信，则这条连接是关键连接（即桥）。找出所有关键连接。
示例：
输入：4 4
1-2, 1-3, 2-3, 3-4
输出：3-4
（删去 1-2 或 1-3 或 2-3，{1,2,3} 仍然连通；只有 3-4 是桥）
✅ 完整解答
直接使用 5.2.13 节的 Tarjan 桥检测算法：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<pair<int,int>> adj[MAXN]; // {邻居, 边编号}
int disc[MAXN], low[MAXN], timer_val = 0;
bool visited[MAXN];
vector<pair<int,int>> bridges;
void dfs(int u, int par_edge) {
visited[u] = true;
disc[u] = low[u] = ++timer_val;
for (auto [v, eid] : adj[u]) {
if (eid == par_edge) continue; // 不走来时的边（用边ID区分，处理重边）
if (!visited[v]) {
dfs(v, eid);
low[u] = min(low[u], low[v]);
if (low[v] > disc[u]) // 桥的判断
bridges.push_back({u, v});
} else {
low[u] = min(low[u], disc[v]);
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
for (int i = 1; i <= n; i++)
if (!visited[i]) dfs(i, -1);
cout << "关键连接数：" << bridges.size() << "\n";
for (auto [u, v] : bridges)
cout << u << " - " << v << "\n";
return 0;
}
注意用「边 ID」而非「父节点」 来避免走回来时的边，这样可以正确处理重边（两个节点之间有多条边的情况）。
题目 5.2.11 — 记忆化 DFS：最长递增路径 🟡 中等
题目： 给定 N×M 矩阵，每次可以向上下左右移动到严格更大的相邻格子。求矩阵中最长递增路径的长度。
示例：
输入：3 3
9 9 4
6 6 8
2 1 1
输出：4（路径 1→2→6→9）
✅ 完整解答
思路： 因为只能往更大的格子走，不会有环，图是 DAG。用记忆化 DFS：memo[r][c] = 从 (r,c) 出发的最长路径长度。
#include <bits/stdc++.h>
using namespace std;
int R, C;
vector<vector<int>> mat;
vector<vector<int>> memo;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
int dfs(int r, int c) {
if (memo[r][c] != 0) return memo[r][c]; // 已计算过
memo[r][c] = 1; // 至少长度为 1（只含自身）
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
if (mat[nr][nc] > mat[r][c]) { // 严格更大才能走
memo[r][c] = max(memo[r][c], 1 + dfs(nr, nc));
}
}
return memo[r][c];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> R >> C;
mat.assign(R, vector<int>(C));
memo.assign(R, vector<int>(C, 0));
for (auto& row : mat) for (int& x : row) cin >> x;
int ans = 0;
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
ans = max(ans, dfs(r, c));
cout << ans << "\n";
return 0;
}
为什么不需要 visited 数组？ 因为路径单调递增，不可能访问同一个格子两次，天然无环。memo[r][c]!=0 就代表已经算过了。
题目 5.2.12 — 多源 BFS：地图离源距离 🟡 中等
题目： N×M 网格，有些格子是障碍 #，有些是出口 E，其余是空格 .。
对所有空格，输出到最近出口的步数（不能穿越障碍），若无法到达输出 -1。
✅ 完整解答
思路： 多源 BFS——把所有出口以距离 0 同时压入队列，BFS 向外扩散。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int R, C; cin >> R >> C;
vector<string> grid(R);
for (auto& row : grid) cin >> row;
vector<vector<int>> dist(R, vector<int>(C, -1));
queue<pair<int,int>> q;
// 所有出口以距离 0 入队
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (grid[r][c] == 'E') {
dist[r][c] = 0;
q.push({r, c});
}
int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r+dr[d], nc = c+dc[d];
if (nr<0||nr>=R||nc<0||nc>=C) continue;
if (grid[nr][nc]=='#') continue;
if (dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r][c] == '#') cout << "# ";
else if (grid[r][c] == 'E') cout << "E ";
else cout << dist[r][c] << " ";
}
cout << "\n";
}
return 0;
}
题目 5.2.13 — 综合挑战：迷宫中的钥匙 🔴 困难
题目： N×M 迷宫，包含：
S：起点E：终点#：墙.：空地a~f：钥匙（小写字母）A~F：锁住的门（大写字母，需要对应钥匙才能进入）
从 S 走到 E，求最少步数。钥匙捡起后一直携带。
提示： 状态需要扩展为 (行, 列, 已携带的钥匙集合)，用 BFS 搜索最短路。
✅ 完整解答
关键：状态 = (位置 + 钥匙集合)。钥匙只有 6 把，用 6 位二进制整数表示集合（0~63）。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int R, C; cin >> R >> C;
vector<string> grid(R);
for (auto& row : grid) cin >> row;
int sr, sc, er, ec;
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++) {
if (grid[r][c] == 'S') { sr=r; sc=c; }
if (grid[r][c] == 'E') { er=r; ec=c; }
}
// dist[r][c][keys] = 步数，keys 是 6 位位掩码
vector<vector<vector<int>>> dist(R, vector<vector<int>>(C, vector<int>(64, -1)));
queue<tuple<int,int,int>> q;
dist[sr][sc][0] = 0;
q.push({sr, sc, 0});
int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
while (!q.empty()) {
auto [r, c, keys] = q.front(); q.pop();
if (r == er && c == ec) {
cout << dist[er][ec][keys] << "\n";
return 0;
}
for (int d = 0; d < 4; d++) {
int nr = r+dr[d], nc = c+dc[d];
if (nr<0||nr>=R||nc<0||nc>=C) continue;
char cell = grid[nr][nc];
if (cell == '#') continue;
// 门：需要对应钥匙
if (isupper(cell) && !(keys & (1 << (cell-'A')))) continue;
// 捡钥匙
int nkeys = keys;
if (islower(cell)) nkeys |= (1 << (cell-'a'));
if (dist[nr][nc][nkeys] == -1) {
dist[nr][nc][nkeys] = dist[r][c][keys] + 1;
q.push({nr, nc, nkeys});
}
}
}
cout << -1 << "\n"; // 无法到达
return 0;
}
状态空间大小： R × C × 64 = 最多 50×50×64 = 160,000 个状态，BFS 可以高效处理。
示例追踪：
起点 S(0,0)，keys=0
→ 走到 a(0,1)：keys = 0 | (1<<0) = 1（拿到钥匙 a）
→ 走到 A(1,1)：keys=1，A 对应位 0，keys&1=1 ✓，可以通过
→ 最终到达 E