图的遍历（BFS 与 DFS）

谷歌的网络爬虫访问 example.com，发现它链接到 a.com、b.com，然后访问 a.com，发现它链接到 c.com、d.com……这个过程叫做图遍历：系统地访问图中每一个可达节点，不重复、不遗漏。

从地图导航到代码编译器的依赖分析，从社交网络的朋友推荐到游戏中的寻路——几乎所有涉及"关系"的问题，背后都有图遍历在工作。

两种基本策略#

图遍历有两种基本策略，区别在于探索的顺序：

广度优先搜索（BFS，Breadth-First Search）：先把距起点 1 步的所有节点访问完，再访问距离 2 步的，以此类推——像水波一样逐层扩散。

深度优先搜索（DFS，Depth-First Search）：沿一条路一直走到底，走不通了再回头换路——像探迷宫时选一条走道走到尽头。

BFS：最短路径的保证#

BFS 使用队列实现，保证按距离顺序访问节点：

from collections import deque

def bfs(graph, start): visited = {start} queue = deque([start]) while queue: node = queue.popleft() print(node) # 处理节点 for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) ```

以下图为例：

    A
   / \
  B   C
 / \   \
D   E   F
```

BFS 从 A 开始的访问顺序是 A → B → C → D → E → F，按层次划分则是：层次 0 = {A}，层次 1 = {B, C}，层次 2 = {D, E, F}。

BFS 的关键性质：第一次到达一个节点时，经过的路径是从起点到该节点的最短路径（按边数计）。这使 BFS 天然适合求无权图中的最短路径。

复杂度：时间 $O(V + E)$（$V$ = 节点数，$E$ = 边数），空间 $O(V)$（队列最大存整层节点）。

DFS：递归探索的本质#

DFS 使用栈实现（或用递归，递归调用栈本质也是栈）：

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)  # 处理节点
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited
```

同样的图，DFS 从 A 开始的访问顺序（取决于邻居顺序）是 A → B → D → E → C → F。DFS 处理节点的时机有三种选择： - 前序（Pre-order）：访问节点时处理（进入节点时） - 后序（Post-order）：回溯时处理（所有子节点处理完后） - 中序（In-order）：只适用于二叉树，左-根-右

复杂度：时间 $O(V + E)$，空间 $O(V)$（最深递归栈深度，最坏情况为图的直径）。

DFS 的副产品：边的分类#

DFS 不只给出一个访问顺序，它在遍历过程中还把所有边分成四类，而这正是后续一连串 DFS 应用的原材料：

• 树边（Tree Edge）：走向未访问节点的边，构成 DFS 树（或森林）
• 后向边（Back Edge）：指向当前节点的祖先——有向图中发现后向边当且仅当图中有环
• 前向边（Forward Edge）：指向已完成后代的非树边
• 横叉边（Cross Edge）：连接两个无祖先关系的分支

分类的实现只需给节点打三色标记：未访问（白）、进行中（灰，在递归栈上）、已完成（黑）。遍历到一条边时看另一端的颜色即可归类。拓扑排序（后序逆序）、环检测（找后向边）、强连通分量（low-link 追踪可达的最早祖先），读的都是同一份分类信息——这些都是一次 DFS 的副产品，不是各自独立的新算法。

应用对比#

同一个骨架：连通分量与二分图判定#

BFS 和 DFS 的价值不止于"访问所有节点"——一批看似无关的图问题共享同一个骨架：跑一次遍历，在遍历过程中顺手维护一点额外信息，答案就掉出来了。

连通分量：从未访问的节点反复启动遍历，每次覆盖的节点集合就是一个连通分量。无需任何新机制，只是"遍历没走完就再启动一次"。

二分图判定：图是二分的（顶点可二染色使相邻顶点不同色）当且仅当不含奇环。BFS 的分层结构直接给出染色方案：起点染红色，第 1 层染蓝色，第 2 层染红色……逐层交替，遍历中只需检查每条边两端是否异色。为什么"同层相邻"是唯一的失败形态？因为 BFS 树中任何非树边两端的层差至多为 1——若层差达到 2，浅层节点扩展时会先发现那个深层节点，矛盾。于是发现同层相邻边，就意味着它与两条到起点的路径共同构成奇环，判定失败。

拓扑排序：DFS 的重要应用#

对有向无环图（DAG），拓扑排序是把所有节点排成一行，使每条有向边都从前到后指向。典型应用是课程选修的先修顺序、软件包安装的依赖关系、编译器确定代码编译顺序。

DFS 实现拓扑排序：对图做 DFS，记录每个节点的"完成时间"（DFS 回溯时），按完成时间从大到小排序即是拓扑序。

def topological_sort(graph):
    visited = set()
    order = []

def dfs(node): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs(neighbor) order.append(node) # 后序：所有子节点处理完后才加入

for node in graph: if node not in visited: dfs(node) return list(reversed(order)) ```

双向 BFS：加速搜索#

对于两端已知的最短路径问题（如"从 A 到 B 最短几步"），可以从两端同时 BFS，当两个搜索波前相遇时停止。在均匀图中，双向 BFS 的时间复杂度从 $O(b^d)$ 降至 $O(b^{d/2})$（$b$ 为分支因子，$d$ 为最短路径长度）——这可以是数量级的差距。Google Maps 的路径规划使用此类技术的变种。

迭代加深：BFS 与 DFS 的折中#

BFS 保证最短但空间 $O(b^d)$ 常常不可承受；DFS 空间只要 $O(d)$，但不保证最短，还可能一头扎进深分支。迭代加深搜索（IDDFS，Iterative Deepening DFS）——Korf（1985）对其作了系统分析——的做法简单到近乎偷懒：先做深度上限为 0 的 DFS，再做上限为 1 的，再做上限为 2 的……直到找到目标。

第一次听说这个策略的人几乎都会问：重复展开前面所有层，不是巨大的浪费吗？算一笔账就放心了。在分支因子为 $b$、深度为 $d$ 的树上，节点总数约 $b^{d+1}/(b-1)$，而仅最后一层就占 $b^d$——树的绝大多数节点集中在最底层。IDDFS 重复展开的只是上面的小层，最底层只展开一次；总展开量与 BFS 之比约为 $b/(b-1)$：$b=2$ 时约 2 倍，$b=10$ 时只多约 11%。用"最多翻倍的重复劳动"换来"BFS 的最优性 + DFS 的 $O(d)$ 空间"——在内存是瓶颈的搜索问题（拼图、自动规划）里，这是决定性优势。把深度上限换成启发式估价值的上限，就是 IDA\*，经典拼图求解的标准方法。

A* 与启发式搜索：BFS 的扩展#

纯 BFS 按边数寻找最短路径，不考虑边的权重。当边有不同权重（如道路距离）时，需要 Dijkstra 算法（见shortest-path-dijkstra）。

但在实际地图导航中，还可以利用启发信息（如目标方向的直线距离）来优先探索"看起来更接近目标"的路径，大幅减少探索节点数——这是 A\* 算法的核心思想（Hart et al., 1968）。A\* 是游戏 AI 寻路的标准算法，也用于机器人规划。

强连通分量：DFS 的深层应用#

有向图中有一个重要问题：找出所有强连通分量（Strongly Connected Components，SCC）——即每个顶点都能到达同一个分量中所有其他顶点的最大子图。

Kosaraju-Sharir 算法（1978）用两次 DFS 解决这个问题：

1. 对原图做 DFS，按完成时间从大到小记录顶点
2. 对转置图（所有边反向）按上述顺序做 DFS，每次 DFS 覆盖的顶点集就是一个 SCC

Tarjan 算法（Robert Tarjan，1972）用一次 DFS 完成，使用栈和"low-link"值追踪可达性。时间复杂度均为 $O(V + E)$。

SCC 的应用： - 社交网络分析：找出互相关注的"小圈子"（用户之间可以相互到达的最大子图） - 程序分析：编译器用 SCC 识别互递归的函数组，分析数据流 - 网页排名：PageRank 的核心计算在 SCC 的有向图缩点（DAG）上进行

最短路径树与 BFS 的正确性证明#

为什么 BFS 第一次到达节点时的路径一定是最短的？

归纳证明： - 层次 0（起点 $s$）：距离 = 0，显然正确 - 层次 $d$：假设所有层次 $< d$ 的节点已有正确最短距离 - 层次 $d$ 的节点 $v$ 被某个层次 $d-1$ 的节点 $u$ 发现：$dist(v) = dist(u) + 1$ - 不可能存在更短路径：若有路径长度 $< d$，$v$ 应在层次 $< d$ 就被发现了

这个证明的关键是 BFS 的FIFO 顺序——队列保证层次 $d$ 的所有节点在层次 $d+1$ 的任何节点之前被处理。

"最短"仅限无权图：边权不同时，BFS 的层次结构不再对应实际距离——需要用 Dijkstra（带权 BFS）。

图遍历的历史#

BFS 的概念最早由 Konrad Zuse 在 1945 年提出（在他为 Plankalkül 语言写的文档中），但现代的 BFS 描述一般追溯到 Edward F. Moore 1959 年用于迷宫求解的工作。

DFS 的系统化则来自 Tarjan 1972 年的工作——他不只提出了 DFS，更揭示了 DFS 树、后向边、前向边、交叉边的结构，以及它们与图的拓扑性质（SCC、桥、割点）之间的精确对应。Tarjan 凭借这项工作（以及后来对数据结构的大量贡献）在 1986 年获得 ACM 图灵奖。

代价与争议#

递归 DFS 的栈溢出风险：对非常深的图（如长链），递归 DFS 可能栈溢出。解决方法：用显式栈迭代实现，或设置递归深度限制（Python 默认 1000）。

BFS 的内存压力：BFS 需要在内存中保存整个当前层的所有节点。对于分支因子大（每个节点有很多邻居）的图，BFS 可能需要大量内存。这是 DFS 内存占用 $O(d)$（深度）相对 BFS $O(b^d)$ 的优势所在。

图的稀疏性与表示：图可以用邻接矩阵（$O(V^2)$ 空间，随机查询 $O(1)$）或邻接表（$O(V + E)$ 空间，遍历更快）表示。对稀疏图（$E \ll V^2$，如社交网络），邻接表是标准选择；对稠密图（如完全图），邻接矩阵更紧凑。BFS 和 DFS 都更适合邻接表表示：复杂度是 $O(V + E)$ 而非 $O(V^2)$。

跨域连接#

• 图论：深度优先不只是一种访问次序，它在图上诱导出一棵树，并把所有边分成树边、后向边、前向边与横叉边。图的桥、割点与强连通分量全部可以从这个分类直接读出，这才是遍历的理论价值。广度优先给不出同样的结构：它的层次只编码距离，不编码依赖关系。
• 编译器：控制流图上的深度优先后序给出逆拓扑序，直接决定求值与编译顺序；强连通分量把互递归的函数组识别成一个整体，因为组内的数据流必须一起收敛。次序在这里不是效率问题而是正确性问题：顺序错了，数据流分析读到的是一堆尚未定稿的中间结果。
• 传染病建模与监测：接触者追踪就是从确诊者出发的广度优先，层数等于传播代数。但真实接触网络高度聚集，波前会大量重叠——第 $k$ 层的实际人数远小于分支因子的 $k$ 次方，因为许多路径通向同一批人。这解释了追踪为何早期有效、社区传播后失效：波前一旦覆盖整个连通块，"下一层"就不再是新人。
• 流域水文：数字高程模型上每个格点把水交给最陡的下游邻居，得到一张有向无环图；汇流累积量就是按拓扑序做一次遍历，每格把自身与上游的总量传下去。平坦区与洼地会破坏无环性，必须先填洼再排序，否则遍历会陷进环里——这是把连续地形离散化必须付的代价。
• 社会网络分析：社交距离就是广度优先的层数，六度分隔说的是这个数出奇地小。但同一份网络的高聚集性又意味着波前严重重叠，所以"两跳能认识几千人"在算术上成立、在名单上不成立。度量社交可达性时必须区分"路径条数"与"不同的人数"：前者爆炸，后者受限于社群边界。

参考文献#

• Cormen, T. et al. Introduction to Algorithms (CLRS). 3rd ed. 第22章. MIT Press, 2009.
• Sedgewick, R. & Wayne, K. Algorithms. 4th ed. 第4章（图算法）. Addison-Wesley, 2011.
• Tarjan, R. E. Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2), 1972.（DFS 理论的奠基论文）
• Korf, R. E. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. Artificial Intelligence 27(1), 1985.（IDDFS/IDA* 的奠基论文）
• Hart, P. et al. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 1968. （A* 算法原始论文）

延伸阅读#

• Even, S. & Even, G. Graph Algorithms. 2nd ed., Cambridge University Press, 2011.（1979 年初版的修订本，由 Guy Even 整理、Richard Karp 作序，从 DFS/BFS 一路讲到网络流）
• Skiena, S. S. The Algorithm Design Manual. 3rd ed., Springer, 2020.（"战争故事"体的实战视角，讲清什么问题该用哪种遍历）