专题：图的遍历 —— 性质与陷阱

本讲定位：图论系列第二讲，全系列使用频率最高的一讲。第 01 讲给了 DFS 和 BFS 两份能跑的模板，本讲回答一个更难的问题：它们为什么对，以及在哪里会悄悄错掉。内容看起来简单——DFS 十行、BFS 十二行——但这十几行里藏着三个学生几乎必踩的坑，本讲每一个都做了实测：vis 在出队时才标记（完全图上入队次数暴涨 162 倍，且若 dis 无条件覆盖则 20/20 全错）、递归 DFS 爆栈（8 MB 栈实测 25 万层通过、30 万层段错误）、用带 vis 的 DFS 冒充最短路（5000 组随机图错 1982 组，最大高估 10 层）。正面结论只有一条，但它撑起后面十几讲：无权图上 BFS 的层数就是最短路——本讲给出归纳法证明并与 Floyd 对拍 3800 组全部一致。最后是三个立刻能用的套路：洪水填充的反向思维、连通块预处理、反向建图。文中所有代码经 g++ -O2 -std=c++14 -Wall 编译运行，P1443、P1141、P3916 三道例题均与洛谷官方样例逐字符核对，P3916 另与暴力对拍 5500 组。

前置知识：第 01 讲的存图与第 7 节那两份遍历模板（必须先学，本讲所有代码都建立在它们之上）；递归函数的执行过程；queue 的 push/front/pop/empty（见顶层 06-linear-structures.md）。

适合对象：CSP-J 复赛备考。本讲全部内容标 J，是 CSP-J 图论题的绝对主力，也是后面 14 讲的公共工具。没有可跳过的部分。

1. 从一道题说起

P1443 马的遍历：$n \times m$ 的棋盘（$n, m \le 400$），一只马在 $(x, y)$，问它走到棋盘上每一个格子至少要走多少步（马走”日”字，走不到输出 $-1$）。

第一反应可能是这样：从起点开始，把马能走的 8 个方向全试一遍，试到目标为止，记录最少步数。

void dfs(int x, int y, int step) {
    if (step >= ans[x][y]) return;         // 已经有更优解了
    ans[x][y] = step;
    for (int k = 0; k < 8; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (在棋盘内) dfs(nx, ny, step + 1);
    }
}

这份代码答案是对的，但它会把同一个格子反复更新很多次——本质是在枚举所有可能的走法。$400 \times 400 = 160000$ 个格子，每个格子 8 个方向，路径数量是指数级的，step >= ans[x][y] 这一行剪枝救不了它。

而第 01 讲那份 BFS 模板只需要每个格子被访问一次，总共 $160000 \times 8 \approx 1.3 \times 10^6$ 次操作，瞬间出解。

差别在哪？在于一个 bool 数组——以及用对它的方式。本讲就是关于这件事的。

2. vis：$O(n+m)$ 到底是从哪来的

核心思想：给每个点记一个”来过了吗”。来过就不再进去。于是每个点恰好被处理一次，每条边恰好被检查一次（无向图两次），总复杂度 $O(n + m)$。

不判 vis 会怎样？在无向图上，$u$ 走到 $v$，$v$ 又能走回 $u$，$u$ 再走到 $v$……无限递归，立刻栈溢出。哪怕图是 DAG（无环），不判 vis 也会让路径数变成指数级：

1 ─→ 2 ─→ 4 ─→ 6        不判 vis: 从 1 到 6 有 2^k 条路径, 每条都走一遍
 \   ↗ \   ↗              判 vis  : 每个点只进一次, 共 n 次
  → 3     → 5

vis 的本质是把”枚举所有路径”变成”枚举所有点”。

这句话是整个图论算法体系的第一块基石，值得多想一层：路径的数量是组合爆炸的（上图 $k$ 层就有 $2^k$ 条），而点的数量是 $n$。vis 做的事情就是用”每个点只保留一次访问”这个约束，把一个指数级的搜索空间压成线性的。代价是——你只能得到”每个点被访问过一次”这个信息，得不到”到每个点的所有走法”。第 6 节那个”DFS 求最短路”的错误，根子就在这里：它想要的信息已经被 vis 扔掉了。

后面的拓扑排序（第 04 讲每个点入队一次）、Dijkstra（第 05 讲每个点确定一次）、Tarjan（第 13 讲每个点分配一个 dfn），全都是”每个点只处理有限次”这个思路的变体。

两种走法：vis 决定了”哪些点会被访问”（答案唯一：起点所在连通块的全部点），但访问顺序取决于你用什么容器装”待访问的点”：