第 23 章 最小生成树 (Minimum Spanning Trees)
核心结论
-
MST 问题：连通无向图 G = (V, E) 含权函数 w 找总权重最小的生成树 T（无环 + 连通 + |V|−1 边）。
-
通用贪心 (Generic-MST)：维护集合 A ⊆ T* (MST)；每步找「安全边」(safe edge) 加入 A 直到 T* 完成——这是 MST 类算法的统一框架。
-
切 (Cut) 与安全边：定理 23.1 = 跨切的「轻边」(light edge) 必安全；Corollary 23.2 = 连接不同树分量的轻边必安全。
-
Kruskal 算法：按边权升序扫描；跨连通分量（用 union-find）即加入 MST；时间 O(E lg E) = O(E lg V)，二分堆实现。
-
Prim 算法：从根 r 出发，把「连接到树的最轻边」对应的顶点加入；用 min-priority queue；时间 O(V lg V + E lg V) = O(E lg V)（二叉堆） / O(E + V lg V)（Fibonacci 堆）。
-
正确性：通用贪心 + 切 + 安全边证明 MST；Kruskal 与 Prim 都基于此；Fibonacci 堆使 Prim 与 Kruskal 在稠密图上具竞争力。
|
本章主旨
本章是图论中工程价值最高的算法之一——最小生成树 (MST)。它把第 16 章的贪心思想形式化为「通用方法 + 切 + 安全边」框架，并由此得到 Kruskal 和 Prim 两个不同策略的算法（边权排序 vs. 优先队列）。三种实现策略对应不同图密度：二叉堆 Prim O(E lg V) 适合稀疏图、二叉堆 Kruskal O(E lg V) 适合中等图、Fibonacci 堆 Prim O(E + V lg V) 适合稠密图。MST 是网络设计、聚类、近似算法的重要子程序；第 23 章还给出了连接「一般图论」「拟阵理论」「贪心算法」的统一视角——MST 是「图拟阵」（无环边集构成独立集族）的最大权独立子集。本章 2 节 = 通用方法 (23.1) + 两种算法 (23.2)，是图论算法中最具教学价值的章节。 |
一、核心概念
本章围绕 5 个核心概念展开：先建立 MST 问题与通用贪心方法（23.1），再深入 Kruskal 与 Prim 两种具体算法（23.2）。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
MST 定义与权重 |
连通无向图 G = (V,E) 上的无环连通边子集 T，权 \(w(T) = \sum_{(u,v) \in T} w(u,v)\) 最小； |
T |
= |
V |
− 1。 |
§23.1 引子；不唯一（图 23.1 例：替换一条边权相同即可）。 |
通用贪心 (Generic-MST) 与安全边 |
维护 A ⊆ T*；找安全边 (u,v) 加入 A 直到 T* 完成 — 由切定理 23.1 给出「安全边」识别规则。 |
§23.1;关键不变量：A ⊆ 某 MST。 |
切 (Cut) 与轻边 (Light Edge) |
切 (S, V\ S) 划分 V；不与 A 交叉的切「尊重 A」；跨切边中权重最小者称「轻边」；定理 23.1：轻边 ∩ 切 = 安全边。 |
§23.1;推论 23.2：跨连通分量的轻边安全。 |
Kruskal 算法 |
边按权升序；跨不同 union-find 集 → 加 A 并 UNION；O(E lg E) = O(E lg V)；适合「边稀疏、union-find 自然归并」的图。 |
§23.2 伪代码 MST-KRUSKAL;调用 MAKE-SET / FIND-SET / UNION;用 §21 启发式 α(V)。 |
Prim 算法 |
从根 r 出发生长单树；min-key 顶点出队 → 加 A；松弛邻接顶点降低 key；二叉堆 O(E lg V) / Fibonacci 堆 O(E + V lg V)。 |
二、详细笔记
2.1 MST 与通用贪心方法
What：连通无向图 G = (V, E) 含权函数 w：E → ℝ；MST = 总权重最小的生成树（无环连通子集，|E_T| = |V| − 1）。
Why：MST 是网络设计中最朴素的优化问题；通用贪心方法给出统一框架——任何具体算法（Kruskal、Prim）都是这个框架的不同「安全边选择策略」实例。
How：
| 要素 | 定义 |
|---|---|
切 (S, V\S) |
把 V 划分为两部分 |
跨切 |
一端在 S、另一端在 V\S 的边 |
切尊重 A |
A 中无跨切边（即 A 不「切」两端） |
轻边 |
跨切边中权重最小者（多条同权时任取） |
安全边 |
加入 A 不破坏「A ⊆ 某 MST」的不变量 |
安全边定理：
证明概要（cut-and-paste）：设 T* 含 A 但不含 (u,v)；(u,v) 与 T* 中 u 到 v 的路径上某边 (x,y) 都在跨切边——T* \{(x,y)} ∪ {(u,v)} 仍是 MST 且包含 A ∪ {(u,v)}。
Corollary 23.2：A 是森林（每连通分量是树）时，跨某连通分量到另一分量的轻边是安全的。
When：作为 MST 类算法的「公理化」框架——任何正确算法都可分析为「按某种规则选安全边」。
Example：CLRS 图 23.2 — 切 (S, V\S) = ({a,b,d,e,h,i}, {c,f,g})；跨切边集合 { 4,8,11,8,7,9,10,14,21,2,7,6 }，最小是 (d,c) 权重 4（唯一轻边）。
2.2 Kruskal 算法
What：Kruskal 按边权升序扫描每条边 (u, v)，若两端不在同一连通分量则加入 MST（即用 union-find 检查）；时间 O(E lg E)。
Why：Kruskal 是 MST 算法中最简单直观的一个——「边从小到大、跨分量就合并」；与第 21 章 union-find 天然配合，给出 O(E α(V)) 的归并成本。
How：
| 步骤 | 操作 |
|---|---|
复杂度 |
初始化 |
A = ∅；每顶点 MAKE-SET |
O(V) |
排序 |
边按权升序 |
O(E lg E) |
主循环 |
for (u,v) ∈ E sorted: if FIND-SET(u) ≠ FIND-SET(v): A.addu,v; UNION(u, v) |
O(E α(V)) |
总 |
— |
O(E lg E) = O(E lg V)（E < V²） |
贪心性质证明（推论 23.2 视角）：每步加入 (u, v) 时，A 是森林，跨某分量 C 到其他分量的轻边——因此 (u, v) 必安全。
When：中等密度图 (|E| ≈ few × |V|);并行 MST 计算（Borůvka 风格）也常基于 Kruskal。
Example：CLRS 图 23.4 — Kruskal 按权重扫描 11 条边，加 (b,d)、(e,g)、(a,c)、(h,i)、(a,b)、(e,f)、(b,c) 7 条 → MST 总权 37。
2.3 Prim 算法
What：Prim 从根 r 出发，把跨越「已建树」与「未建顶点」的最小权边对应的顶点加入树中；用 min-priority queue 维持候选；时间 O(E lg V)（二叉堆）/ O(E + V lg V)（Fibonacci 堆）。
Why：Prim 与 Dijkstra 单源最短路径结构上极为相似——都是「每次取 min-key 顶点 + 松弛邻边」；主要差异是「累积路径权重」（Dijkstra）vs.「当前边权重」（Prim）。
How：
| 步骤 | 操作 |
|---|---|
二叉堆复杂度 |
初始化 |
每顶点 v.key = ∞、v.π = NIL；r.key = 0；Q = V |
O(V) (BUILD-MIN-HEAP) |
主循环 |
while Q ≠ ∅: u = EXTRACT-MIN(Q); for each v ∈ Adj[u]: if v ∈ Q and w(u,v) < v.key: v.π = u; v.key = w(u,v) |
EXTRACT-MIN O(lg V) × V; RELAX (DECREASE-KEY) O(lg V) × E |
总 |
— |
O(V lg V + E lg V) = O(E lg V) |
Fibonacci 堆 |
|
DECREASE-KEY 摊还 O(1) |
O(E + V lg V) |
不变量：(1) A = {(v, v.π) : v ∈ V \ {r} \ Q}；(2) V \ Q = 已加入树的顶点；(3) v.key（v ∈ Q）= v 到树的最小跨切边权重。
贪心性质证明：每次加入 u 时 (u, u.π) 跨切 (V\Q, Q)，且是最小跨切边——因此是轻边 → 安全边。
When：稠密图（|E| ≈ |V|²）；与 Dijkstra 兼容，实现上常共享代码。
Example：CLRS 图 23.5 — 从 a 出发，依次加 (a,h)、(h,b) 或 (a,b)、(b,c) 或 (h,i) 等（权最小时任取其一）→ 总权 37。
2.4 复杂度对比与优化
What：三个主流 MST 实现的复杂度对比——二叉堆 Kruskal/Prim 都是 O(E lg V)，Fibonacci 堆 Prim O(E + V lg V)；进一步优化（Fredman-Tarjan、Chazelle）可达 O(E α(E,V)) 甚至线性（随机化）。
Why：稠密图上 Fibonacci 堆 Prim 优于其他；稀疏图上 Kruskal 简单且快；选择决定实现复杂度。
How：
| 算法 | 复杂度 |
|---|---|
适用 |
Kruskal（二叉堆排序） |
O(E lg V) |
边稀疏或中等 |
Prim（二叉堆） |
O(E lg V) |
边稀疏或中等 |
Prim（Fibonacci 堆） |
O(E + V lg V) |
边稠密 |
Borůvka + 优先级 |
O(E lg V) |
并行 / 外部 |
Chazelle |
O(E α(E,V)) |
理论最优 |
Karger-Klein-Tarjan |
O(V + E) 期望 |
When：根据图密度选实现；数据库系统常用 Kruskal（外部排序边）；实时网络设计常用 Prim。
Example：稠密图 |E| = 10⁷、|V| = 10⁴ 时：Kruskal/Prim O(10⁷ lg 10⁴) ≈ 4·10⁸；Fibonacci Prim O(10⁷ + 10⁴·14) ≈ 10⁷ — 提升 40 倍。
2.5 MST 的扩展与变体
What：MST 是基础构件；其他扩展包括次优 MST、瓶颈 MST、动态 MST（加/减边更新）、有向 MST（最小树形图 / Edmonds 算法，单独见算法导论第 23 章后习题）。
Why：在网络设计、聚类、近似算法、Steiner 树近似中 MST 是关键工具；理解 MST 后才能学习次优/瓶颈变体。
How：
| 扩展 | 定义 / 关系 | 应用 |
|---|---|---|
次优 MST |
第二小权重的生成树（T'；可与 T 差 1 边）；O(V²) 或更优 |
容错网络 |
瓶颈 MST |
最大边权最小的生成树；MST 必是瓶颈 MST |
网络可靠性 |
动态 MST |
加/减边后增量更新 MST（复杂） |
|
动态网络 |
最小树形图 |
有向图指定根的最小生成树（Edmonds 算法） |
任务调度流 |
度约束 MST |
|
每顶点度有限制；NP-hard 或特殊条件 |
VLSI 布线 |
When：NP-hard 度约束 MST 时改用近似；动态 MST 多用于 OS 路由协议（RIP、OSPF）；次优 MST 常作 MST 鲁棒备份。
Example：CLRS 问题 23-1 给次优 MST 的 O(V²) 算法（用 max[u,v] 数组 + 替换候选）。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 23 章 MST))
MST问题
无环连通
w(T)最小
|V|-1边
通用贪心
A⊆T*
安全边
切定理
切与轻边
S,V\S划分
轻边跨切最小
安全=轻边
Kruskal
边升序扫描
union-find
O(E lg V)
Prim
单树生长
min-queue
二叉堆O(ElgV)
Fibonacci堆
DECREASE-KEY
摊还O(1)
O(E+V lg V)
扩展
次优MST
瓶颈MST
动态MST
最小树形图
应用
网络设计
聚类
近似算法
== 五、重点与易错点
. MST 与最短路径树（SPT）的区别：MST 是「最小总边权和」、SPT 是「源到各点的最短路径」——两者一般不同。
. MST 不唯一（图 23.1 例）：当有同权边时存在多个 MST；最小化「最大边权」（瓶颈）则是唯一的。
. 通用贪心的「安全边」不一定要最小权——定理 23.1 是「任何跨切的轻边都安全」（其中跨切时「轻」=「最小权」）。
. Kruskal 用 union-find 检查「跨分量」，Prim 用 min-priority queue 取「跨树最轻」——前者按边处理，后者按顶点处理。
. 排序是 Kruskal 的瓶颈：O(E lg E)；用计数排序 / 桶排序可以把边权小范围（如 §23.2-4）降到 O(E + V)。
. Prim 的 root 选取任意；时间复杂度与 root 无关——通常取 v=1。
. Prim 在稠密图上的「二叉堆」实现是浪费：邻接矩阵 + 朴素查找 O(V²) 更直接（CLRS 习题 23.2-2）。
. 不直接支持「调整边权后增量更新」——动态 MST 是难题（Holm-de Lichtenberg-Thorup O(lg⁴ V) 随机化）。
. MST 与「Steiner 树」不同：Steiner 允许加额外中间顶点；MST 不允许；Steiner 是 NP-hard 但有 2-近似。
. MST 与「最小度生成树」「有界度生成树」区别：后者常 NP-hard（除非度界 ≥ 2）。
. CLRS 用「安全边 + 切」证明 MST 是通用贪心案例——把第 16 章的拟阵抽象具体化为图拟阵 M_G。
. 在数据库 JOIN 查询优化中可借鉴 MST 的「最小代价连接」思想——但实际用更复杂的代价模型。
. 一些 MST 实现在并行/外部场景用 Borůvka 风格 + Kruskal 排序边块；TimeForwardProcessing 等用 I/O 高效算法（不在 CLRS 范围）。
. MST 是「网络可靠性」「Steiner 树 2-近似」「k-MST（k 个顶点的 MST）」的算法基础——理解 MST 后能迁移到这些变体。