图上的 DFS 与 BFS、连通性

1 这一章拿来练手的问题

给一张无向图（n 个点、m 条边，可能有自环，也可能有重边，而且不保证连通） 和一个起点 s，求： ① 图里有几个连通块； ② 从 s 出发，到每个点最少要走几条边（走不到的输出 -1）。

输入第一行是 n m s，接下来 m 行每行两个端点。

2 手算一遍：8 个点、9 条边，起点故意不是 1 号

8 9 3          ← 8 个点、9 条边、起点是 3 号
1 2
2 3
1 3
3 4
4 5
5 1
2 2            ← 自环
1 2            ← 和第 1 条重复（重边）
6 7

先把它画出来：1-2-3-4-5-1 连成一个环（还多一条 1-3 的弦）， 6-7 单独连在一起，8 号点一条边都没有。

• 连通块：{1,2,3,4,5}、{6,7}、{8} —— 一共 3 个。 ⚠ 8 号点虽然孤零零的，但它自己就是一个连通块。
• 从 3 号出发的距离： 3 号自己是 0；它的邻居 2、1、4 都是 1； 5 号要经过 4（或者经过 1）才到，是 2； 6、7、8 号根本走不到，是 -1。

3 / 1 1 0 1 2 -1 -1 -1 —— 这组数后面每一步都会回来验。

3 暴力：两问都用「完全不是搜索」的思路做一遍

点「运行 ▶」看结果

标准答案又一次换了思路（第 9 章那条规矩）：

• 连通块用朴素并查集：它根本不「走」图，只是把每条边的两个端点合并到一起， 最后数还剩几个根。（并查集第 36 章才正式讲，这里用的是最朴素的版本。）
• 最短路用枚举所有简单路径：从 s 出发一条路走到黑，每走到一个点就拿 「当前这条路的长度」去更新它的答案，然后回溯换一条路 —— 第 4 章那一套。

4 实测：暴力慢在哪 —— ★ 旋钮不是点数，是边数

先说一件容易搞错的事。「枚举所有简单路径」听起来是「和点数有关」的指数级， 但真正让它爆炸的是平均度数：点越挤，绕法越多。

本机实测（./genBig 30 <边数>，点数一直是 30 不变）：

（最后两行每次跑上下浮动一两成，量级是稳的。）

★ 点数一个都没动，只多加了 15 条边，暴力就慢了两百多倍。

自己动手把那个旋钮拧一遍（genDense 就是「点数固定 30、边数当参数」的 genBig）：

5 ★ 关键一步：把第 13 章的代码原样搬过来

先把第 13 章那份 DFS 摆出来，只看它的核心循环：

它的心脏是这一段：

for (int d = 0; d < 4; d++) {                 // 上下左右四个方向
    int x = i + dx[d], y = j + dy[d];
    if (x < 0 || x >= n || y < 0 || y >= m) continue;   // 出界
    if (g[x][y] != '1') continue;                       // 是水
    if (vis[x][y]) continue;                            // 走过了
    dfs(x, y);
}

换到图上，它塌成一行：

for (int v : g[u]) {                          // 邻接表里那一行
    if (vis[v]) continue;                     // 走过了
    dfs(v);
}

6 正解：一份代码，两问都解决

点「运行 ▶」看结果

跑出 3 / 1 1 0 1 2 -1 -1 -1，和第 2 步手算的一样。复杂度 O(n + m) —— 每个点进出一次，每条边被两端各看一次，正好是第 29 章那张表里「表扫一遍 = 2m」那一行。

7 ★ 动画：左边是网格，右边是图，一个 DFS 同时在两幅画上走

左边是一张 5×5 的小地图（11 个陆地格），右边是它转成的图： 11 个点被均匀摆在一个圆上，边成了乱七八糟的弦 —— 看着和网格毫无关系。

但请注意：两幅画是同一帧数据画出来的。同一个 DFS、同一个访问顺序、同一批颜色。 右边那个圈之所以看着不像网格，只是因为我把点画到别处去了 —— 图不在乎点画在哪里，只在乎谁和谁有边。

这张地图有 4 个连通块，其中 3 个是孤立点（被水围住的单格陆地）。 把下拉框切到「✗ 只从有边的点发起」，4 块当场塌成 1 块。

8 ★ 跨章节交叉验证：把第 13 章那张地图真的转成图

光看动画还不够。这一步要动真格的：把第 13 章那张 8×8 地图转成一张图的输入文件， 再交给第 6 步那份 fast.cpp —— 它对「网格」二字一无所知。

点「运行 ▶」看结果

那张 8×8 地图里有 36 个陆地格 → 36 个点、33 条边， (0,0) 是 1 号点，(7,7) 是 36 号点。接上管道：

./gridToGraph < map.txt | ./fast

9 四种把最短路写错的方式

下拉框里那四个错误版本，各对应下面一份代码。先看动画怎么错的，再看代码错在哪。

点「运行 ▶」看结果

跑出 2 1 0 1 2（1 号点应该是 1）。第 14 章说过这个错误「会退化成暴力」， 但在图上它更狠：答案本身就是错的。

道理在动画的计数器里：一个点可能被好几个邻居同时看见，于是被塞进队列好几次， 每塞一次都会重写一遍它的距离 —— 而后写的那次不一定更近。 默认这张图上，正确写法入队 5 次（正好等于走得到的点数）， 出队才标记入队 8 次，多出来的 3 次全是在改写别人的答案。

★ 「入队时标记」保证的是：一个点只被记一次距离，而且是第一次 —— 也就是最短的那次。

点「运行 ▶」看结果

跑出 2 1 0 4 3 —— 4 号点明明是 3 号的直接邻居，却被记成了 4。

点「运行 ▶」看结果

这两个错误在第 12 步会变成这一章最贵的一课 —— 它们的死活完全取决于数据长什么样。

10 第五种错法：孤立点不算一块

点「运行 ▶」看结果

跑出 2 块（正确是 3）。写法本身看着很讲道理： 「一个点连边都没有，还搜它干嘛？」—— 可它自己就是一个连通块。

回到第 7 步那个动画，把下拉框切到这一档：网格里那三个被水围住的单格陆地全被跳过了， 4 块塌成 1 块。在网格里它叫「一格孤岛」，在图里它叫「孤立点」，是同一样东西。

11 ⚠ 一个网格题里碰不到的坑：递归 DFS 会爆栈

点「运行 ▶」看结果

两种改法，这份代码里各用了一次：

• 数连通块干脆改用 BFS 染色。「哪些点连在一起」跟走的顺序毫无关系， DFS 能做的 BFS 一样能做，而队列在堆上，没有深度问题。 ★ 能用 BFS 就别用递归 DFS —— 这是这一章最实用的一条。
• 真需要 DFS 的顺序时，用手写栈把递归摊开： 栈里存 (当前点, 下一条要看的边是第几条)，正好就是递归帧里那两个局部变量。

⚠ 别把这理解成「递归不能用」。n 只有几万时递归版更短更好读，用它就是了。 n 上十万，先想一想这个深度。知道界在哪，比背「递归不安全」有用得多。

g++ -O2 -std=c++17 -o genBig genBig.cpp
g++ -O2 -std=c++17 -o fast fast.cpp
g++ -O2 -std=c++17 -o fastIter fastIter.cpp
./genBig 500000 > big.txt
./fast     < big.txt   # ✗ Segmentation fault
./fastIter < big.txt   # ✓ 0.7 秒
./fastIter depth < big.txt | tail -1   # 看看它压了多少层

12 ★ 对拍：两个「顺手」的写法，一次掩盖三个 bug

300 轮实测，五个错误版本：

13 这一章可以带走的四样东西

// 网格：每次重新回答「谁是我的邻居」
for (int d = 0; d < 4; d++) { …出界？是墙？走过了？… }

// 图：邻接表提前把这件事做完了
for (int v : g[u]) { …走过了？… }

14 自测