1.3 图的遍历：DFS与BFS
1.3 图的遍历：DFS 与 BFS
本节摘要：图的遍历指从某顶点出发按规则访问所有可达顶点，两大骨架是深度优先搜索（DFS）与广度优先搜索（BFS）。DFS 沿一条路径走到底再回溯，天然适合连通性判断与环检测；BFS 借助队列逐层扩散，在无权图上直接给出最短路径，是第 2 章 Dijkstra 的思想原型。本节给出两者的执行模拟、代码骨架与选型对比。
你能学到什么
阅读完本节，你应当能够：
- 手工模拟 DFS 与 BFS 在给定图上的访问顺序；
- 写出基于递归与基于队列的两份遍历代码；
- 说明 visited 标记为什么必不可少、什么情况下会死循环；
- 用 BFS 求解无权图的单源最短路径，并解释它为什么是对的；
- 用 DFS 判断连通性与检测环。
一、没有 visited 会发生什么
从顶点 A 出发访问图，A 有邻居 B，B 有邻居 A。如果没有任何记忆，访问序列就是 A、B、A、B……永远停不下来。图的遍历与树的遍历最大的不同就在这里：树里每个节点只有唯一父指针，图里可以绕环回到已访问的点。所以一切图遍历的标配是一张 visited 表——每个顶点只在第一次到达时处理一次。
遍历看似只是"走一遍"，但它是图算法的原子操作：
- 判断两个点是否连通（从一点 DFS，看能否到达另一点）；
- 数出连通分量的个数（对每个未访问点各启动一次遍历）；
- 检测图中有无环；
- 为有向无环图做拓扑排序（第 2 章 DAG 最短路的预处理）；
- 无权图最短路径（BFS 的本职工作之一）。
二、深度优先搜索：一条道走到黑
DFS 的策略是"能深则深"：从当前顶点任选一个未访问的邻居前进，走到无路可走时回溯到上一个还有未访问邻居的顶点，继续换路。它像探索迷宫时沿右手墙一直走——撞墙才回头。
执行模拟（沿用 1.2 节的图，边 A-B、A-C、B-C、B-D，邻居按字母序）：
访问 A → 访问 B（A 的第一个邻居） → 访问 C（B 的第一个未访问邻居） → C 的邻居 A、B 都访问过，回溯到 B → 访问 D（B 的下一个未访问邻居） → 回溯到 B，再回溯到 A；A 的邻居已全部访问，结束 DFS 序：A B C D
递归实现极短：
def dfs(graph, node, visited): visited.add(node) print('访问', node) for neighbor in graph[node]: if neighbor not in visited: dfs(graph, neighbor, visited) dfs(graph, 'A', set()) # 覆盖一个连通分量
若图可能不连通，外层再套一个循环，对每个还没 visited 的顶点重新启动 DFS，顺便就能数出连通分量个数。复杂度上，邻接表实现的 DFS 是顶点数加边数的线性时间——每个顶点进一次 visited，每条边最多被两端各看一次；若用邻接矩阵，找邻居要扫整行，退化为顶点数平方。
DFS 的应用谱系很宽：连通分量、环检测（无向图中遇到"已访问且不是父节点"的邻居即有环）、拓扑排序、割点与桥、以及各类回溯搜索（走迷宫、八皇后）。
三、广度优先搜索：一圈一圈往外扩
BFS 的策略是"先近后远"：借助队列，先访问起点，再依次访问距离为 1 的所有点、距离为 2 的所有点……像水面的涟漪逐层扩散。邻居同样按字母序时，上图从 A 出发的 BFS 序是 A、B、C、D——与 DFS 相同纯属巧合，图的层次结构决定了两者在更多图上会给出不同顺序。
from collections import deque def bfs(graph, start): dist = {start: 0} queue = deque([start]) while queue: node = queue.popleft() for neighbor in graph[node]: if neighbor not in dist: dist[neighbor] = dist[node] + 1 queue.append(neighbor) return dist # 每个点的最少边数距离
复杂度同样是线性时间（邻接表）。注意代码里我们顺手记录了 dist——每个顶点首次被标记时的层数，恰好就是从起点出发的最少边数。这就引出了本节最重要的结论：
在无权图上，BFS 就是最短路径算法。 原因在于"逐层扩散"保证了第一次到达某顶点时走的必然是最少边数的路径：所有更短的路径只可能来自更浅的层，而更浅的层早已处理完毕。原始文集中把 BFS 比作"逐层扩展的园丁"，并明确指出无权图最短路径的时间复杂度就是顶点数加边数的线性级别——这个结论是通往第 2 章的桥：一旦边上有了权重，"先到的层"未必更便宜，BFS 的贪心失效，Dijkstra 用优先队列把"逐层"升级为"按累计代价"扩展，故事从那里继续。
四、DFS 与 BFS 全方位对比
| 维度 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（递归栈或显式栈） | 队列 |
| 访问顺序 | 一条路径到底，回溯换路 | 按到起点的距离逐层 |
| 空间特征 | 最坏正比于路径长度（深图危险） | 最坏正比于最宽一层的顶点数 |
| 无权最短路 | 不能直接得到 | 直接得到（首次标记即最短） |
| 连通性/环检测 | 天然胜任 | 也可做，但实现不自然 |
| 拓扑排序 | 经典做法（出栈逆序） | 按入度剥离 |
| 典型应用 | 迷宫、回溯、割点、拓扑 | 层次遍历、最短路、社交"几度人脉" |
选型经验：问"到某点最少几步"，BFS；问"这堆点连不连通、有没有环、能不能拓扑排序"，DFS；问"所有方案里挑最优"（解空间搜索），DFS 加回溯。两者复杂度同级，差别在得到的信息类型。
一个实用提醒：DFS 的递归版本在链状图（十万级深度的路径）上会爆栈，工程实现要么改成显式栈迭代，要么限制深度。BFS 则要警惕"最宽一层"过大——社交网络的"一度好友"可能有几十万，队列内存不可小看。
⚠️ 常见坑：BFS 里"出队时才标记 visited"。这会让同一个顶点在被访问前被多个邻居重复入队，队列膨胀、效率下降，极端情况下结果照对但白白多跑许多轮。正确姿势是入队时就标记。
💡 关键直觉：DFS 与 BFS 是同一棵"遍历树"的两种生长方式——DFS 长得又深又窄，BFS 长得又宽又浅。后面的 Dijkstra 是 BFS 的加权版（队列换优先队列），Kruskal 的并查集是 DFS 连通性判断的增量版。遍历骨架认牢了，进阶算法都是它的变奏。
五、深入一层：遍历树与图的"骨架"透视
两种遍历都不只是"访问顺序"，它们各自在图上隐式生成一棵遍历树：起点为根，每个非起点顶点通过"第一次发现它的那条边"连到树上。DFS 生成的树又深又窄，BFS 生成的树又宽又浅，同一张图、同一份邻居顺序，两种树的形态差异极大。
遍历树是理解后续算法的钥匙。BFS 树上"根到每个顶点的树路径"就是无权最短路径——这不是巧合，而是 2.4 节结论的证明骨架。DFS 树则把边分成四类：树边（构成树本身）、前向边（指向后代）、后向边（指向祖先）、交叉边（指向已处理完的其他分支）——后向边的存在与否正是环检测的原理：无向图中遇到"已访问且非父"的邻居、有向图中遇到指向"递归栈中祖先"的边，都意味着环。拓扑排序的 DFS 版本同样建立在树与边的这个分类上。
一个手工练习值得做：拿 6 个顶点、8 条边的图，分别画出 DFS 树与 BFS 树，再把非树边标上类别。十分钟后你对"遍历到底得到了什么信息"的理解会上一个台阶。
常见疑问解答
迭代版 DFS 怎么写？和递归版行为一致吗？
用显式栈替换递归栈：弹出一个点、处理、把未访问邻居压栈。行为上有一个细节差异——压栈顺序与递归的访问顺序相反（后压的先访问），需要与递归版对齐时把邻居反序压栈即可。大规模图务必用迭代版，递归深度是链状图的定时炸弹。
BFS 能不能顺便记录"最短路径本身"？
能。给每个顶点记一个前驱（入队时由谁发现的），到达终点后沿前驱回溯即得路径。这本质上就是把 BFS 树的树路径取出来，代码只需两行增量。这个技巧在 2.4 节会正式升级为最短路径的完整输出。
遍历复杂度说"线性"，为什么我的代码远慢于线性？
三个常见嫌疑：邻接矩阵存储下找邻居本来就是平方级；visited 用了低效的容器（如列表的成员判断是线性的，应换集合或哈希）；或者在循环里做了额外工作（如频繁拼接路径字符串）。用 1.2 节的选型检查存储，用集合替换列表，通常能找回数量级。
多个连通分量时，遍历结果怎么组织？
外层循环对每个未访问顶点各启动一次遍历，每次启动天然对应一个连通分量。把这些结果收集起来，就同时得到了"分量个数 + 每个分量的成员表"——这是后续生成森林、社区粗划分的输入。
动手实验：双栈实现逐层输出
一道能同时练透两种遍历的经典练习：按层打印图的节点（层与层之间分隔）。BFS 版需要记录"当前层还剩几个、下一层有几个"两个计数器；也可以故意用 DFS 实现——维护"当前层路径栈"与"已发现最深层数"，回溯时弹栈。两份代码写完对比，你会对"层"这个概念在两种遍历里的不同呈现（BFS 天然分层、DFS 靠深度记账）有肌肉记忆级的理解。进阶变体：求"离起点最远的点"（BFS 最后一层）、判断图是否二分（BFS 染色，同层不冲突）——都是面试的常客。
遍历的三个变体提醒
其一，多源 BFS：把一批起点同时入队，得到"离任一起点最近"的距离——多仓库覆盖分析的标准做法。其二，双向 BFS：从起点与终点同时扩散，相遇即停，复杂度从"全图"降到"两球体积和"，点对点查询的实用加速。其三，限制深度的 DFS：只搜到深度 k（迭代加深），在解空间巨大但解很浅的搜索里省内存。三个变体都不改变"visited 加队列/栈"的骨架，只调整起点集合与终止条件——骨架扎实，变体即插即用。
遍历结果为什么每次运行顺序不同？
如果你发现两次遍历的访问序不一样，先查两个来源：一是邻居的存储顺序不稳定（链表插入顺序、哈希遍历序都会漂移），固定顺序需要显式排序或用有序容器；二是多起点场景下起点集合的处理顺序。这几乎从来不是算法错误，但在需要可复现输出的测试里会咬人——固定邻居顺序是图算法单元测试的基本功。
核心回顾
- visited 必须有：图有环，不记忆就会死循环；每点只处理一次是线性复杂度的保证。
- DFS 走到底再回溯：递归实现极简，适合连通性、环检测、拓扑排序与回溯搜索。
- BFS 逐层扩散：借助队列，首次标记某点时的层数即无权图最短边数。
- 无权最短路 = BFS：线性时间解决，这一结论直接启发出第 2 章的 Dijkstra。
- 复杂度：邻接表下两者均为顶点数加边数线性；邻接矩阵下退化为平方级。
- 空间风险：DFS 怕深（爆栈），BFS 怕宽（最宽一层爆队列），实现时按图形态预警。
- 标记时机：BFS 应在入队时标记 visited，避免重复入队。
遍历解决的是"能不能到、几步到"。下一章给边加上价格，问"怎么到最便宜"——最短路径的完整战场。