第 22 章 基本图算法 (Elementary Graph Algorithms)
核心结论
-
图的两种表示：邻接表 (Adj) 适合稀疏图 (|E| ≪ |V|²)，存储 O(V + E)；邻接矩阵 (A) 适合稠密图或 O(1) 边查询，存储 O(V²)；本章默认邻接表。
-
BFS（广度优先搜索）：从源点 s 用 FIFO 队列按层探索；计算 s 到每个顶点的最短边数距离 + 构造 BFS 树；时间 O(V + E)。
-
DFS（深度优先搜索）：递归探索每个顶点 + 用颜色（白 / 灰 / 黑）和时间戳 d / f 记录；构造 DFS 森林（含树边 + 后向 / 前向 / 交叉边）；时间 O(V + E)。
-
DFS 括号定理：任两顶点的时间区间要么不相交、要么严格嵌套——刻画「祖先-后代」的层次关系。
-
DAG 拓扑排序：调用 DFS 按「完成时间降序」插入链表前部——DAG 当且仅当无后向边（定理 22.11 + 22.12）；时间 O(V + E)。
-
强连通分量 (SCC)：两次 DFS——先在 G 上记录完成时间 u:f，再在 G^T 上按 u:f 降序启动；每棵 DFS 树 = 一个 SCC（定理 22.16）；时间 O(V + E)。
|
本章主旨
本章是图算法的奠基——把图论的核心搜索 / 排序 / 分量三类操作一次性给出：BFS 求最短路径（无权图） + DFS 提供结构信息 + 拓扑排序解决 DAG 偏序 + SCC 把任意有向图化为 DAG。DFS 是最强大的子程序——几乎所有线性时间的图算法都以它为内核：拓扑排序、SCC、Tarjan SCC（等价但单趟）、articulation points、bridges 等。本章的 5 节是后续图算法（第 24-26 章的 MST、最短路径、流量）的统一基础——SCC 的「分量图是 DAG」这一关键定理 (Lemma 22.13) 多次被引用。本章用希腊字母命名顶点（ι、ω）保持 CLRS 风格；时间戳 (d/f) + 颜色 + 父指针是 DFS 的标配属性。 |
一、核心概念
本章围绕 6 个核心概念展开：先建立图的两种表示（22.1），然后是 BFS（22.2）、DFS（22.3），再到拓扑排序（22.4）和 SCC（22.5）两个 DFS 的应用。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
邻接表 / 邻接矩阵 |
邻接表 = 数组 Adj[1..V] 每位存链表；空间 O(V+E)；邻接矩阵 = V×V 矩阵 A；空间 O(V²)；默认邻接表。 |
§22.1;稀疏图首选邻接表、稠密图或需 O(1) 边查询选矩阵。 |
BFS 最短路径 |
从源 s 用 FIFO 队列按距离递增访问；计算 s 到所有可达顶点的最短边数 + BFS 树；时间 O(V+E)。 |
§22.2 伪代码;三色（白/灰/黑）+ 距离 d + 父指针 π;BFS 树 = π 子图。 |
DFS 探索 + 时间戳 |
递归探索每个白顶点；时间戳 d（发现）+ f（完成）+ 颜色；构造 DFS 森林；时间 O(V+E)。 |
§22.3 DFS / DFS-VISIT 伪代码;d/f 给出括号结构定理。 |
边分类（DFS） |
树边、后向边、前向边、交叉边；d/f 时间戳判定；定理 22.10：无向图只有树边和后向边。 |
§22.3;定理 22.11：DAG 当且仅当无后向边。 |
拓扑排序 |
DAG 中所有边(u,v) ⇒ u 在 v 之前的线性序；算法：DFS 完成时插链表前部；时间 O(V+E)。 |
§22.4;完成时间降序 ⇒ 拓扑序。 |
强连通分量 (SCC) |
G vs G^T 两次 DFS，按 u:f 降序；每棵树 = 一个 SCC；分量图 GSCC 是 DAG（Lemma 22.13）；时间 O(V+E)。 |
§22.5;Tarjan 单趟 SCC 是另一个等价但更精炼的版本。 |
二、详细笔记
2.1 图的表示
What：图 G = (V, E) 的两种标准表示——邻接表 Adj[1..V]（每条链表存邻接顶点）和邻接矩阵 A（V×V 矩阵）。
Why：选表示 = 时间空间权衡的最朴素的版本——邻接表省空间、邻接矩阵 O(1) 边查询。
How：
| 表示 | 空间 | 边查询时间 |
|---|---|---|
适用 |
邻接表 |
O(V + E) |
O(deg(u)) |
稀疏图 / 本书默认 |
邻接矩阵 |
O(V²) |
O(1) |
稠密图、所有对最短路径（Floyd-Warshall） |
加权扩展 |
邻接表中存 (v, w) 对、矩阵存 w(u,v) |
— |
定向 vs 无向：邻接表中无向图每边出现两次（u → v 和 v → u）。
When：|E| ≪ V² 时邻接表；|E| ≈ V² 时邻接矩阵；所有对最短路径 / 传递闭包时邻接矩阵。
Example：CLRS 图 22.1 — 5 顶点 7 边无向图；邻接表 Adj[1] = (2,5)、Adj[2] = (1,4,5) 等；邻接矩阵沿主对角对称（无向图性质）。
2.2 BFS 与最短路径
What：BFS(G, s) 从源 s 出发，按距离递增用 FIFO 队列访问顶点；为每个可达顶点计算最短边数距离 v:d 和记录父指针 v:π；构造 BFS 树（仅树边）。
Why：BFS 在无权图上替代 Dijkstra 求单源最短路径；亦是 Prim MST 算法（第 23 章）的灵感来源。
How：
-
初始化：除 s 外所有顶点染白、d = ∞、π = NIL；s 染灰、d = 0；入队 s。
-
循环：u = DEQUEUE(Q)；for each v ∈ Adj[u]：若 v 白，染灰、v.d = u.d + 1、v.π = u、ENQUEUE(v)；u 出队后染黑。
-
复杂度：初始化 O(V)；每顶点入队出队一次 O(V)；每条边扫描一次 O(E)；总 O(V + E)。
-
正确性（定理 22.5）：BFS 终止时 v.d = δ(s, v) 最短路径距离；BFS 树（π 子图）是从 s 到所有可达顶点的最短路径树。
-
引理 22.3：BFS 队列中 d 值单调不增（相邻 d 差 ≤ 1）。
When：无权图最短路径；作为其他算法的子程序（Prim MST）；社交网络的「度距离」计算。
Example：CLRS 图 22.3 — 有向/无向图 BFS 由 u 出发，按距离 0,1,2,3 扩展；BFS 树边只 5 条，跨边仍是图边但不入树。
2.3 DFS 与括号定理
What：DFS(G) 深度优先遍历所有顶点，记录每个顶点的发现时间 d 和完成时间 f；顶点颜色变化：白（未发现）→ 灰（已发现未完成）→ 黑（完成）；DFS 森林由父指针 π 构造。
Why：DFS 是图论算法的「瑞士军刀」——拓扑排序、SCC、articulation points、bridges、biconnected components 都以 DFS 为子程序；时间戳提供完整的层次信息。
How：
| 元素 | 含义 | 用途 |
|---|---|---|
时间戳 v.d |
首次发现（染灰）时 |
括号定理 / 排序关键 |
时间戳 v.f |
完成（染黑）时 |
SCC 中第二次 DFS 排序关键 |
父指针 v.π |
DFS 树中的父 |
树边判定 |
颜色 |
白 / 灰 / 黑 |
边类型判定 |
边类型 |
树 / 后向 / 前向 / 交叉 |
DAG、桥、bcc 等 |
伪代码（核心）：
-
DFS(G): for all v: v.color = WHITE, v.π = NIL; time = 0; for all v: if WHITE DFS-VISIT(v)
-
DFS-VISIT(u): time; u.d = time; u.color = GRAY; for v ∈ Adj[u]: if WHITE v.π = u; DFS-VISIT(v); u.color = BLACK; time; u.f = time
定理 22.7（括号定理）：任两顶点 (u, v)，三选一：（1）区间不相交且互不为后代；（2）u.f < v.f 则 v 是 u 后代；（3）v 是 u 后代类似。
When：图结构分析、拓扑排序、SCC、连通分量、桥、bcc、欧拉回路、关键路径（AOE 网络）。
Example：CLRS 图 22.4 — 有向图 DFS 时间戳：B/C/F 后向边指向祖先、Z 与 Y 是交叉边；S 树根为 1/10。
2.4 拓扑排序
What：DAG G = (V, E) 的拓扑排序 = 顶点的线性序，使每条边 (u, v) 中的 u 排在 v 前；算法：DFS 完成时插入链表前部 → 「完成时间降序」即拓扑序。
Why：拓扑排序把偏序关系扩展为线性序——编译器 DAG 指令调度、make 工具的依赖关系、课程先修关系都基于此。
How：
-
TOPOLOGICAL-SORT(G): DFS(G) 计算 f；每顶点完成时插入链表前；返回链表。
-
复杂度：DFS O(V + E) + 链表插入 O(1) × V → O(V + E)。
-
正确性：定理 22.5 保证 DAG 中每条边 (u, v) 的 v 在 u 的 DFS 中完成后才有 u 完成 → 链表中 v 在 u 前。
-
等价定理 22.11：G 是 DAG 当且仅当 DFS 不产生后向边（自环被视为后向）。
When：DAG 上的依赖关系；任务调度（先决条件）；偏序扩展为线性序。
Example：CLRS 图 22.7 — 教授穿衣 DAG，拓扑序：socks < undershorts < pants < shoes < watch < shirt < belt < tie < jacket。
2.5 强连通分量
What：强连通分量 (SCC) = 有向图中极大子集 C ⊆ V，使 ∀u, v ∈ C：u ↝ v 且 v ↝ u；分量图 GSCC 是 DAG（Lemma 22.13）。
Why：SCC 把有向图压缩为分量图（节点数 ≤ 原节点数），复杂算法可分两阶段：分量内 + 分量图（DAG）。
How：
-
STRONGLY-CONNECTED-COMPONENTS(G):
-
DFS(G) 记录完成时间 u.f
-
计算 G^T
-
DFS(G^T)，主循环按 u.f 降序启动
-
每棵 DFS 树 = 一个 SCC
-
-
复杂度：两次 DFS 各 O(V + E) + G^T 计算 O(V + E) → 总 O(V + E)。
-
关键引理：
-
Lemma 22.13：分量图是 DAG（C 含回路则合并）
-
Lemma 22.14：边 (u, v) 在 G 中跨分量 ⇒ f(C_u) > f(C_v)
-
Corollary 22.15：边在 G^T 中跨分量 ⇒ f(C_u) < f(C_v)
-
-
定理 22.16：第二次 DFS（按 f 降序）的每棵树恰是一个 SCC。
When：把任意有向图化为分量 DAG；2-SAT、循环依赖检测、Web 链接分析都基于 SCC。
Example：CLRS 图 22.9 — 有向图 G 的 SCC：{a,b,e}、{c,d}、{f,g}、{h}；分量图 G^SCC 是 DAG（a→c→f、a→c→h 等）。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 22 章 基本图算法))
表示
邻接表稀疏
邻接矩阵稠密
加权扩展
BFS
FIFO队列
距离d父指针
最短边数
O(V+E)
DFS
递归探索
d/f时间戳
三色变化
括号定理
边分类
树边
后向/前向
交叉边
DAG无后向
拓扑排序
DAG线性序
完成时间降序
O(V+E)
SCC
两次DFS
G^T转置
f降序
分量图DAG
应用
Kruskal
Dijkstra
编译器调度
== 五、重点与易错点
. 「邻接表 vs. 邻接矩阵」选型：稀疏图用表、稠密或需 O(1) 边查询用矩阵；默认邻接表。
. BFS 的「度距离」= 最短边数距离；与加权最短路径（Dijkstra）不同——前者用 FIFO 队列即可，后者需要优先队列。
. BFS 队列中的 d 值始终单调不增（Lemma 22.3）——证明 BFS 正确性的关键。
. DFS 不止一种实现：递归（直接但栈深）、用显式栈模拟（消除递归）；两种等价。
. 时间戳 (d, f) 提供完整括号结构——若有向图 DFS 中 u.d < v.d < v.f < u.f 则 v 是 u 后代（Corollary 22.8）。
. 边类型判定：白 = 树边、灰 = 后向、黑 = 前向或交叉；结合 d/f 时间戳区分前向 vs. 交叉。
. 无向图 DFS 只有树边和后向边（定理 22.10），但「无向图每边需看两次」——常在 DFS-VISIT 中只处理一次以避免误判。
. 拓扑排序的等价：完成时间降序 ↔ 入度为 0 反复删除（CLRS 习题 22.4-5）；前者用 DFS 一次完成，后者可增量更新。
. SCC 算法的关键洞察：转置图 G^T 有相同 SCC 但跨 SCC 边的方向反转；所以按第一次 f 降序第二次 DFS 自动按拓扑序访问分量图。
. Tarjan SCC 算法（CLRS 习题 22.5-? / 实际为单趟基于 low 值）也是 O(V+E) 但只需一次 DFS；适合在线 / streaming 场景。
. SCC 的实际应用：2-SAT 求解（利用分量图）、死锁检测（资源分配图化 SCC）、Web 图链接分析、社交网络社区发现。
. 在生物信息学、版本控制（git merge）、编译器模块依赖等场景，SCC 与拓扑排序结合解决循环依赖问题。
. 本章的「DFS 森林」与「BFS 树」不同——DFS 可能因多连通分量而生成多棵树，所以叫「森林」。
. CLRS 用希腊字母（ι、ω 等）给顶点命名以避免与索引混淆；本章共用 ι（chi）、ω（omega）、υ（upsilon）等。
. 在第 26 章最大流中边反向是核心操作——DFS（也称「增广路径」）用反向边回退流量；SCC 算法中的转置思想与之呼应。