BFS 与 DFS：图的两种基本呼吸方式

上一篇全景图建立了整条路径的概念地图——图能建模什么、有哪些核心问题、用什么范式去解。现在我们正式进入 Part 1”探”的第一站：系统地遍历一张图。

想象你拿到一张全新的地图，第一件事不是量距离或找最短路，而是——走遍所有地方，搞清楚哪里连着哪里。在图论中，这个”走遍所有地方”的操作就是图遍历（graph traversal）。没有高效、系统的遍历手段，后续几乎所有图算法都无从谈起：最短路径需要逐层扩展（BFS），连通分量需要深入探索（DFS），拓扑排序需要后序时间戳（DFS），网络流需要找增广路（BFS）。BFS 和 DFS 不只是两个算法——它们是整个图算法大厦的地基。

算法范式：穷举搜索——系统地访问所有可能，不遗漏

核心问题：怎么系统地访问图的每个角落？

给定一张图 $G = (V, E)$ ， $n = |V|$ 个顶点、 $m = |E|$ 条边。从某个起点 $s$ 出发，我们想做到两件事：

可达性（reachability）：找到从 $s$ 出发能到达的所有节点
系统性（completeness）：保证不遗漏、不重复——每个可达节点恰好访问一次

如果图是连通的（从任意节点能到达任意其他节点），遍历就能访问所有 $n$ 个节点。如果不连通，对每个连通分量分别遍历即可。

这两件事听起来简单，但对于可能有数百万节点和数千万边的图，“随便走走”是不行的——你需要一个策略来决定下一步去哪。不同的策略产生了两种根本不同的遍历方式：

BFS（Breadth-First Search，广度优先搜索）：先处理离起点近的，再处理远的——逐层扩散
DFS（Depth-First Search，深度优先搜索）：一条路走到底，走不通再回头——递归深入

两种策略的时间复杂度相同（ $O(n + m)$ ），但它们的扩展顺序完全不同，导致它们擅长的问题也不同。理解这个区别，是掌握图算法的第一步。

高层直觉：水波 vs 迷宫

在进入具体算法之前，先建立一个几何直觉：

BFS 像一颗石头投入水中 —— 从起点出发，先到达距离为 1 的所有邻居，再到达距离为 2 的所有邻居……一圈一圈向外扩散。每个节点被发现时，它的”层数”就是离起点的最短跳数。

DFS 像在迷宫中探路 —— 沿着一条路一直走到死胡同（没有未访问的邻居），然后回头到最近的岔路口，换一条路继续深入。这种”先深后广”的策略天然地产生递归结构。

两种策略的关键区别在于数据结构：

BFS 用队列（FIFO，先进先出）：先发现的先处理 → 保证逐层
DFS 用栈（LIFO，后进先出）或等价的递归调用栈：后发现的先处理 → 保证深入

BFS 核心：队列、层序、最短跳数

算法流程

BFS 的核心思想可以用一句话概括：把起点放入队列，然后不断从队列取出节点、将其未访问的邻居加入队列，直到队列为空。

详细步骤：

初始化：创建一个队列 $Q$ ，将起点 $s$ 入队，标记 $s$ 为”已发现”
循环：当 $Q$ $Q$ 非空时：
- 从 $Q$ 头部取出一个节点 $u$ （出队）
- 对 $u$ $u$ 的每个邻居 $v \in N(u)$ $v \in N (u)$ ：
  - 如果 $v$ 未被发现：标记 $v$ 为”已发现”，记录 $\text{parent}[v] = u$ ，将 $v$ 入队
结束：队列为空，所有从 $s$ 可达的节点都已访问

用伪代码表示：

BFS(G, s):
    for each v ∈ V:
        visited[v] = false
    visited[s] = true
    Q = empty queue
    Q.enqueue(s)
    while Q is not empty:
        u = Q.dequeue()
        for each v ∈ N(u):
            if not visited[v]:
                visited[v] = true
                parent[v] = u
                Q.enqueue(v)

为什么 BFS 能给出最短跳数？

这是 BFS 最重要的性质，值得仔细理解。

定理（BFS 最短路径性质，CLRS Theorem 20.5）：对于无权图，BFS 从源点 $s$ 到任意可达节点 $v$ 的路径是最短路径（以边数计）。即 $d(s, v) =$ BFS 中 $v$ 的层数。

直觉证明：

BFS 的队列保证了”先发现的先处理”——距离为 $k$ 的节点全部处理完后，才开始处理距离为 $k+1$ 的节点
一个节点被首次发现时，发现它的那条路径一定是最短的（因为更短的路径意味着更早的层，而更早的层已经处理完了）
所以每个节点的 $\text{parent}$ 指针追溯回 $s$ ，就是最短路径

走查示例

下面的交互组件展示了 BFS 和 DFS 在同一张 7 节点图上的完整执行过程。你可以切换 BFS/DFS 模式，逐步观察节点状态和队列/栈的变化。

BFS vs DFS 走查动画

步骤 1/32: 初始状态：所有节点未访问。选择 A 作为起点。

1 / 32

仔细观察 BFS 的走查过程：

第 0 层只有起点 A
第 1 层包含 A 的所有邻居（B、C、G）——它们同时被加入队列
第 2 层是 B 和 C 的邻居中尚未访问的（D、E）
第 3 层是 D 和 E 的邻居中尚未访问的（F）
每个节点被发现的层数就是它到 A 的最短跳数

复杂度分析

时间复杂度： $O(n + m)$ $O (n + m)$ （最坏情况）
- 每个节点入队和出队各一次 → $O(n)$
- 每条边被检查最多两次（无向图中 $(u,v)$ 和 $(v,u)$ ）→ $O(m)$
空间复杂度： $O(n)$ $O (n)$
- 队列最多存储一整层的节点。最坏情况：星形图中队列大小为 $n-1$

DFS 核心：栈/递归、时间戳、发现/结束时间

算法流程

DFS 的核心思想：一条路走到底，走不通再回头。 具体来说：从起点出发，每次选一个未访问的邻居深入，直到没有未访问的邻居（死胡同），然后回溯（backtrack） 到上一个节点，尝试其他未访问的邻居。

DFS 有两种等价实现：

递归版（更自然）：

DFS(G, s):
    for each v ∈ V:
        visited[v] = false
    DFS-Visit(s)

DFS-Visit(u):
    visited[u] = true
    time = time + 1
    d[u] = time           // 发现时间
    for each v ∈ N(u):
        if not visited[v]:
            parent[v] = u
            DFS-Visit(v)   // 递归深入
    time = time + 1
    f[u] = time           // 结束时间

显式栈版：

DFS-Iterative(G, s):
    for each v ∈ V:
        visited[v] = false
    S = empty stack
    S.push(s)
    while S is not empty:
        u = S.pop()
        if not visited[u]:
            visited[u] = true
            for each v ∈ N(u) (reverse order):
                if not visited[v]:
                    S.push(v)

递归版和栈版在访问顺序上有细微差异（因为栈是后进先出，需要反向压入邻居），但核心思想一致。本文后续的分析基于递归版，因为它的时间戳语义更清晰。

时间戳：发现时间与结束时间

DFS 有一个 BFS 没有的独特武器：时间戳。

对于每个节点 $v$ ，DFS 记录两个时间：

发现时间 $d(v)$ （discover time）：DFS 第一次访问到 $v$ 的时刻
结束时间 $f(v)$ （finish time）： $v$ 的所有后代都处理完、DFS 从 $v$ 回溯的时刻

时间从 1 开始递增，每次发现或结束一个节点时 +1。所以对一个 $n$ 节点的图，所有时间戳的范围是 $[1, 2n]$ 。

括号定理

时间戳有一个优美的结构性质：

括号定理（Parenthesis Theorem, CLRS Theorem 20.7）：对于 DFS 树中的任意两个节点 $u$ 和 $v$ ，它们的活跃区间 $[d(u), f(u)]$ 和 $[d(v), f(v)]$ 恰好满足以下三种关系之一：

完全嵌套： $[d(u), f(u)] \subset [d(v), f(v)]$ —— $u$ 是 $v$ 的后代
完全嵌套（反向）： $[d(v), f(v)] \subset [d(u), f(u)]$ —— $v$ 是 $u$ 的后代
完全不相交：两个区间没有交集 —— $u$ 和 $v$ 不在同一条祖先-后代链上

不存在”部分重叠”的情况。 就像合法的括号序列 (()()) 中，任意两对括号要么嵌套要么不相交，不会出现 (() 这样交叉的情况。

这个性质是 DFS 在连通性分析（SCC、桥、割点）中的核心工具，将在 Art. 2: 连通性中详细展开。

复杂度分析

时间复杂度： $O(n + m)$ $O (n + m)$ （最坏情况），与 BFS 相同
- 每个节点被 DFS-Visit 调用恰好一次 → $O(n)$
- 每条边在邻居遍历中被检查最多两次 → $O(m)$
空间复杂度： $O(n)$ $O (n)$ （最坏情况）
- 递归版：调用栈深度最坏为 $n$ （路径图）
- 显式栈版：栈大小最坏为 $n$

边分类：DFS 的结构分析工具

DFS 的真正威力不在于遍历本身，而在于它在遍历过程中对每条边的分类。对于有向图，DFS 将所有边分为四种类型：

四种边类型

设 DFS 正在处理节点 $u$ ，检查边 $(u, v)$ ：

树边（Tree Edge）： $v$ 尚未被发现（ $\text{visited}[v] = \text{false}$ ）。DFS 沿这条边深入 $v$ 。所有树边构成一棵 DFS 树（或 DFS 森林）。
回边（Back Edge）： $v$ 已被发现但未结束（ $d(v) < d(u)$ 且 $f(v)$ 尚未设定）——即 $v$ 是 $u$ 在 DFS 树中的祖先。这条边”回”到了祖先节点。
前向边（Forward Edge）： $v$ 已经结束（ $f(v)$ 已设定），且 $d(u) < d(v)$ ——即 $v$ 是 $u$ 的后代，但这条边不是树边（ $u$ 到 $v$ 在 DFS 树中已经有一条树边路径）。
横跨边（Cross Edge）： $v$ 已经结束（ $f(v)$ 已设定），且 $d(u) > d(v)$ ——即 $v$ 不是 $u$ 的祖先也不是后代，它在另一棵 DFS 子树中。

判定方法

用时间戳可以精确判定：

边 $(u, v)$ 类型	条件
树边	$v$ 未发现
回边	$d(v) < d(u)$ 且 $v$ 未结束
前向边	$d(v) > d(u)$ 且 $v$ 已结束
横跨边	$d(v) < d(u)$ 且 $v$ 已结束

关键洞察：

有向图有环 $\Longleftrightarrow$ DFS 发现了 back edge。 这是环检测最经典的方法。
无向图中只有 tree edge 和 back edge（无 forward 和 cross）——因为如果存在一条边 $(u, v)$ ，在无向图中 DFS 访问 $u$ 时一定会检查 $v$ ，要么 $v$ 未访问（tree edge），要么 $v$ 是祖先（back edge）。
DAG（有向无环图）的 DFS 不产生 back edge —— 这正是判定 DAG 的方法。

BFS 应用模式

BFS 的”逐层扩散”特性催生了一系列应用模式。这里简述每种模式的核心思想，详细展开留给后续专题文章。

1. Flood Fill — 连通区域标记

场景：图像处理中的”油漆桶”工具、扫雷的空白区域展开、地图中的连通区域标记。

做法：从一个种子像素/节点出发，BFS 扩展到所有满足条件的相邻节点（如颜色相同），标记为同一区域。本质上就是 BFS 求连通分量。

复杂度： $O(n + m)$ ，其中 $n$ 是区域内节点数， $m$ 是区域内边数。

2. 多源 BFS — 多起点同时扩散

场景：LeetCode 994 “腐烂的橘子”——多个腐烂源同时向四周扩散；“多个消防站同时响应，求最远点的最近消防站距离”。

做法：将所有源节点同时加入 BFS 的初始队列，然后正常 BFS。效果等价于添加一个虚拟超级源 $s'$ 连接所有真实源节点，然后从 $s'$ 做单源 BFS。

复杂度：仍然是 $O(n + m)$ ，不比单源 BFS 更贵。

3. 无权最短路 — 最少跳数

场景：社交网络中两人之间的”六度分隔”（最少中间人数）、网络中两台主机间的最少跳数。

做法：直接从源节点 BFS，层数就是最短跳数。 $\text{parent}$ 数组可以回溯出具体路径。

复杂度： $O(n + m)$ 。这是无权图最短路的最优算法。

4. 二部图判定 — 奇偶层着色

场景：判断一个图是否是二部图（bipartite）。等价于判断图能否用两种颜色着色，使得每条边的两端颜色不同。

做法：BFS 时给每层交替标记颜色（偶数层红色，奇数层蓝色）。如果某条边的两端颜色相同（同层），则不是二部图。

关键洞察：图是二部图 $\Longleftrightarrow$ 图不含奇数长度的环。BFS 的层序结构天然地提供了这个检测。

5. 网络洪泛/广播

场景：计算机网络中的广播协议——一条消息从一台主机发出，需要到达所有其他主机。

做法：本质上就是 BFS，每个节点收到消息后转发给所有邻居。BFS 的层序保证了消息以最少跳数到达每个节点。

DFS 应用模式

DFS 的”深入回溯”特性和时间戳结构催生了另一套应用模式。

1. 环检测 — back edge 意味着有环

场景：编译器检查头文件的循环依赖、任务调度检查循环等待（死锁检测）。

做法：对有向图做 DFS，如果遇到 back edge（指向当前路径上的祖先），则图有环。对无向图更简单——任何指向已访问且不是父节点的邻居，就是一个环。

核心： $\text{有向图有环} \Longleftrightarrow \text{DFS 存在 back edge}$

2. 拓扑排序引子 — 后序反转

场景：任务调度（先修课程排序）、编译顺序（依赖在前的先编译）。

做法：对 DAG 做 DFS，按照 $f(v)$ （结束时间）的递减顺序排列节点，就是一个合法的拓扑排序。因为如果 $(u, v) \in E$ ，则 $f(u) > f(v)$ （ $u$ 在 $v$ 前结束）。

详细展开：Art. 3: 拓扑排序与 DAG

3. 强连通分量（SCC）引子 — Kosaraju / Tarjan

场景：社交网络中的互相关注群组、网页之间的相互可达性分析。

做法：Kosaraju 算法对图和反转图各做一次 DFS；Tarjan 算法用 DFS + low-link 值在一次遍历中找出所有 SCC。核心都依赖 DFS 的时间戳结构。

详细展开：Art. 2: 连通性

4. 桥与割点引子 — low-link

场景：网络中的关键链路（断了就不连通）、关键路由器（坏了就分裂网络）。

做法：在 DFS 过程中计算每个节点的 low-link 值（通过 back edge 能到达的最早祖先）。如果一条边的终点无法通过 back edge “绕回”起点上方，这条边就是桥。

详细展开：Art. 2: 连通性

5. 回溯搜索 — DFS 搜索解空间

场景：N 皇后问题、排列组合生成、数独求解、图着色。

做法：把所有可能的”选择序列”组织成一棵隐式搜索树，DFS 遍历这棵树。每个节点代表一个”部分解”，叶子代表完整解或不可行解。当发现当前路径不可能产生更优解时，立即回溯（剪枝）。

6. 路径枚举与迷宫求解

场景：找两点之间的所有路径、迷宫从入口到出口的路径。

做法：DFS 天然地沿着一条路走到底再回头，非常适合枚举所有路径。配合 visited 标记的”加入/移除”操作，可以实现回溯式路径枚举。

7. 树遍历 — 前序/中序/后序

场景：二叉树的三种经典遍历方式其实都是 DFS 的特例。

做法：

前序遍历：在 DFS-Visit( $u$ ) 的开头处理 $u$ （发现时间对应前序位置）
后序遍历：在 DFS-Visit( $u$ ) 的末尾处理 $u$ （结束时间对应后序位置）
中序遍历：在二叉树中，先递归左子树，然后处理 $u$ ，再递归右子树

BFS vs DFS：什么时候用哪个？

这是最实用的问题。下面的对比表和经验法则帮助你做出选择：

经验法则

需要最短路径（跳数）→ BFS。BFS 的层序结构天然保证无权图最短路。DFS 不保证。
需要判断/利用环 → DFS。DFS 的 back edge 是检测有向图环的标准方法。BFS 也能检测无向图环，但 DFS 的时间戳提供了更丰富的结构信息。
需要拓扑排序 → DFS。DFS 的后序反转直接给出拓扑序。（BFS 也能做——Kahn 算法基于入度计数，但本质是不同的思路。）
需要连通性结构（SCC、桥、割点）→ DFS。这些全部依赖 DFS 的时间戳和 low-link 值。
需要按距离分层处理 → BFS。比如多源 BFS、二部图判定。
需要枚举所有路径/解空间 → DFS（回溯）。DFS 的递归结构天然适合回溯搜索。
空间受限、图很深 → 注意 DFS 可能栈溢出。对于非常深的图（如 $10^5$ 层的链），递归 DFS 可能导致栈溢出。这时可以用显式栈版 DFS，或者根据问题特点选择 BFS（BFS 的队列大小取决于”宽度”而非”深度”）。

复杂度对比表

维度	BFS	DFS
时间复杂度（最坏）	$O(V + E)$	$O(V + E)$
空间复杂度（最坏）	$O(V)$ （队列 + visited）	$O(V)$ （栈 + visited）
空间特征	正比于图的”宽度”	正比于图的”深度”
无权最短路	保证	不保证
环检测（有向图）	不直接	back edge
时间戳	无	有（ $d$ , $f$ ）
适用于	最短路、层序、广播	环检测、拓扑排序、SCC、回溯

为什么这是一切的基础

BFS 和 DFS 的重要性远超”两个遍历算法”。后续路径中大约 80% 的算法把它们作为核心子程序：

具体来说：

Art. 2: 连通性 完全基于 DFS 的时间戳——SCC 用两次 DFS（Kosaraju）或一次 DFS + low-link（Tarjan），桥和割点用 DFS + low-link
Art. 3: 拓扑排序 的核心就是 DFS 后序反转
Art. 6: 最短路径 中 Dijkstra 的”最近优先”扩展策略是 BFS 的加权推广
Art. 12: 网络流 中 Ford-Fulkerson 用 BFS 找增广路（Edmonds-Karp 变体），保证多项式时间
Art. 8: 社区发现 的标签传播本质上是修改过的 BFS
Art. 13: 匹配 中 Hopcroft-Karp 交替使用 BFS 和 DFS

理解 BFS 和 DFS，就获得了理解这些高级算法的”通行证”。

🔁 迭代机器视角 — BFSEQ: 方程 / 不动点

Graph	原图
State[v]	visited (Boolean)
SELECT	FIFO
COMBINE	遍历邻接表 → 标记已发现
重入	无
TERMINATE	Frontier 空
生命周期	Unseen → Queued → Done
求解方法	FI

→ 框架详解：Art. 0A — 图上的通用迭代机器

🔁 迭代机器视角 — DFSEQ: 方程 / 不动点

Graph	原图
State[v]	visited + 时间戳 (d, f)
SELECT	LIFO
COMBINE	遍历邻接表 → 标记已发现 + 时间戳
重入	无
TERMINATE	Frontier 空
生命周期	Unseen → Active → Done
求解方法	FI

💡 对比: BFS: 同一框架，仅 SELECT 不同（FIFO vs LIFO）

→ 框架详解：Art. 0A — 图上的通用迭代机器

总结

本文建立了图算法最核心的基础设施——BFS 和 DFS：

BFS（队列/FIFO）：逐层扩散，保证无权最短路，适合距离相关问题
DFS（栈/递归/LIFO）：递归深入，产生时间戳（ $d$ , $f$ ），适合结构分析
边分类：DFS 将有向图的边分为树边、回边、前向边、横跨边——back edge $\Leftrightarrow$ 有环
括号定理：DFS 时间区间要么嵌套要么不相交，是连通性分析的基础
时空复杂度：两者均为 $O(V + E)$ 时间、 $O(V)$ 空间
选择法则：“最短/最近”→ BFS；“完整探索/时间戳/回溯”→ DFS

BFS 和 DFS 是图的两种”呼吸方式”——一种向外扩张，一种向内深入。掌握了它们，你就拥有了探索任意图结构的能力。

下一篇 Art. 2: 连通性将展示 DFS 的时间戳和 low-link 如何成为分析图连通结构的利器——找出强连通分量、桥和割点。

实现指引

算法	库	函数/方法
BFS	NetworkX	`nx.bfs_edges(G, source)`, `nx.bfs_tree(G, source)`
DFS	NetworkX	`nx.dfs_edges(G, source)`, `nx.dfs_tree(G, source)`
BFS 最短路径	NetworkX	`nx.shortest_path(G, source, target)` (无权图默认 BFS)
BFS 层序	NetworkX	`nx.bfs_layers(G, source)`
DFS 前序/后序	NetworkX	`nx.dfs_preorder_nodes(G)`, `nx.dfs_postorder_nodes(G)`
BFS	scipy	`scipy.sparse.csgraph.breadth_first_order(graph, i_start)`
DFS	scipy	`scipy.sparse.csgraph.depth_first_order(graph, i_start)`
BFS/DFS	igraph	`g.bfs(vid)`, `g.dfs(vid)`