最小生成树：最便宜地连通所有人

Part 2”量”建立了一整套度量工具：最短路径量距离、中心性量重要性、社区发现量归属、图相似量结构、团与密子图量致密。但”量”是描述性的——告诉你图是什么样的。

现在进入 Part 3”优”——图上的组合优化。不再只是观察，而是要做决策：从海量可能中选出最好的方案。第一个问题，也是组合优化最经典的入门问题：

给定一张加权无向图 $G = (V, E)$ ，选择哪些边，用最小的总权重把所有节点连通起来？

这就是最小生成树（Minimum Spanning Tree, MST）问题。它无处不在——铺设连接所有城市的光缆网络、设计最低成本的电路板连线、构建层次聚类的树形结构——本质上都在回答”用最少的代价把所有人连到一起”。

更重要的是，MST 是贪心算法的典范。在最短路径中，Dijkstra 的贪心只在非负权时有效，Bellman-Ford 用迭代逼近作为后备。而在 MST 问题上，贪心总是能给出最优解——这个优美的事实背后有深刻的结构性原因（拟阵理论），理解它将为你分析”何时贪心有效”提供强大的理论武器。

算法范式：贪心（Kruskal、Prim、Boruvka）

核心问题：最便宜的连通方案

形式化定义

给定连通的加权无向图 $G = (V, E)$ ， $n = |V|$ ， $m = |E|$ ，每条边 $e$ 有权重 $w(e) \geq 0$ 。

生成树（spanning tree） $T$ 是 $G$ 的一个子图，满足：

$T$ 包含 $G$ 的所有 $n$ 个顶点
$T$ 是连通的
$T$ 是无环的（即是一棵树）

这三个条件等价于： $T$ 恰好有 $n - 1$ 条边，且连通。

最小生成树（MST）是所有生成树中边权总和最小的那个：

$T^* = \arg\min_{T \text{ 是生成树}} \sum_{e \in T} w(e)$

为什么不是简单问题？

一张 $n$ 个节点的完全图有 $n^{n-2}$ 棵不同的生成树（Cayley 公式）。 $n = 20$ 时就有 $20^{18} \approx 2.6 \times 10^{23}$ 种可能——暴力枚举不可行。MST 算法的精妙之处在于：用贪心策略直接构造最优解，完全绕过枚举。

核心思路：割性质与环性质

为什么贪心能构造出最优的生成树？答案归结为两个互补的性质——它们是所有 MST 算法正确性的基石。

割性质（Cut Property）

割（cut） $\delta(S)$ 是一个划分 $(S, V \setminus S)$ （ $\emptyset \neq S \subsetneq V$ ）所跨越的边集——即一端在 $S$ 、另一端在 $V \setminus S$ 的所有边。

割性质：对于图 $G$ 的任意割 $\delta(S)$ ，如果某条跨越边 $e$ 是该割中权重严格最小的（假设权重互不相同），那么 $e$ 一定属于 $G$ 的唯一 MST。

直觉：要连通 $S$ 和 $V \setminus S$ ，至少得选一条跨越边。既然必须选一条，为什么不选最轻的？

证明思路（反证法）：假设 MST $T^*$ 不包含割中最轻边 $e = (u, v)$ 。 $T^*$ 中一定有另一条跨越边 $e'$ 连接 $S$ 和 $V \setminus S$ （因为 $T^*$ 连通）。把 $e$ 加入 $T^*$ 形成一个环，这个环必然包含 $e'$ （因为 $e$ 和 $e'$ 都跨越同一个割）。删除 $e'$ 、保留 $e$ ，得到的仍然是生成树，但权重更小——矛盾。

环性质（Cycle Property）

环性质：对于图 $G$ 中的任意环 $C$ ，如果某条边 $e$ 是 $C$ 中权重严格最大的，那么 $e$ 一定不属于任何 MST。

直觉：环中最重的边是”多余的”——删掉它，环中的其他边仍然保证连通性，而且总权重更小。

证明思路（反证法）：假设 MST $T^*$ 包含环 $C$ 中的最重边 $e$ 。删除 $e$ 把 $T^*$ 分成两个连通分量，形成一个割。 $C$ 中一定还有至少一条其他边 $e'$ 跨越这个割（因为 $C$ 在 $e$ 两侧各有部分）。用 $e'$ 替换 $e$ ，得到权重更小的生成树——矛盾。

两个性质如何指导算法？

Kruskal：按权重从小到大检查边。如果一条边连接两个不同的连通分量，它就是某个割的最轻边 → 选入（割性质）。如果连接同一分量，它是某个环的最重边 → 丢弃（环性质）。
Prim：从一个节点出发，每次从”树内节点”到”树外节点”的割中选最轻边 → 选入（割性质）。
Boruvka：每个连通分量同时选它的割中最轻边 → 全部选入（割性质的并行应用）。

Kruskal 算法：排序 + 并查集

核心思想

Kruskal 算法（1956）的策略极其直觉：

把所有边按权重从小到大排序。依次检查每条边：如果它连接两个不同的连通分量，就选入 MST；如果连接同一分量（选入会形成环），就跳过。

关键问题是如何快速判断”两个节点是否在同一分量”以及”合并两个分量”——这正是并查集（Union-Find / Disjoint Set Union）数据结构的用武之地。

算法流程

Kruskal(G):
    将 E 按权重排序
    初始化并查集：每个节点是独立分量
    MST = 空集

    for each edge (u, v, w) in sorted order:
        if Find(u) ≠ Find(v):       // 不同分量
            MST = MST ∪ {(u, v)}
            Union(u, v)              // 合并分量
        // else: 跳过（会形成环）

    return MST

并查集（Union-Find）

并查集维护一组不相交集合，支持两个核心操作：

Find(x)：返回 $x$ 所在集合的代表元素（根）
Union(x, y)：合并 $x$ 和 $y$ 所在的两个集合

朴素实现每次操作 $O(n)$ （最坏情况下树退化为链）。两个优化将均摊复杂度降到几乎常数：

路径压缩（Path Compression）：在 Find 操作中，让路径上的每个节点直接指向根。下次再查，一步到位。

Find(x):
    if parent[x] ≠ x:
        parent[x] = Find(parent[x])  // 路径压缩
    return parent[x]

按秩合并（Union by Rank）：Union 时把较矮的树挂到较高的树下面，防止树的高度增长过快。

Union(x, y):
    rx = Find(x), ry = Find(y)
    if rx == ry: return
    if rank[rx] < rank[ry]: parent[rx] = ry
    elif rank[rx] > rank[ry]: parent[ry] = rx
    else: parent[ry] = rx; rank[rx]++

两者结合后，每次操作的均摊时间复杂度为 $O(\alpha(n))$ ，其中 $\alpha$ 是逆 Ackermann 函数（inverse Ackermann function）。 $\alpha(n)$ 增长极其缓慢——对于宇宙中所有原子的数量（约 $10^{80}$ ）， $\alpha(n) \leq 4$ 。实践中可以视为 $O(1)$ 。

复杂度分析

排序： $O(m \log m) = O(m \log n)$ （因为 $m \leq n^2$ ， $\log m \leq 2\log n$ ）
并查集操作： $m$ 次 Find + 至多 $n - 1$ 次 Union = $O(m \cdot \alpha(n))$
总计： $O(m \log m)$ ，瓶颈在排序

数值走查

考虑 7 个节点的加权无向图（与交互组件中使用的相同图）：

边按权重排序：C-F(1), A-E(2), D-G(2), B-C(3), F-G(3), A-B(4), E-F(4), B-E(5), C-D(6), F-D(7)

C-F(1)：C 和 F 在不同分量 → 选入。分量： $\{A\}, \{B\}, \{C,F\}, \{D\}, \{E\}, \{G\}$
A-E(2)：A 和 E 在不同分量 → 选入。分量： $\{A,E\}, \{B\}, \{C,F\}, \{D\}, \{G\}$
D-G(2)：D 和 G 在不同分量 → 选入。分量： $\{A,E\}, \{B\}, \{C,F\}, \{D,G\}$
B-C(3)：B 和 C 在不同分量 → 选入。分量： $\{A,E\}, \{B,C,F\}, \{D,G\}$
F-G(3)：F 在 $\{B,C,F\}$ ，G 在 $\{D,G\}$ ，不同分量 → 选入。分量： $\{A,E\}, \{B,C,F,D,G\}$
A-B(4)：A 在 $\{A,E\}$ ，B 在 $\{B,C,F,D,G\}$ ，不同分量 → 选入。分量： $\{A,B,C,D,E,F,G\}$

已选 6 = $n - 1$ 条边，MST 完成！总权重 = $1 + 2 + 2 + 3 + 3 + 4 = 15$ 。

剩余边 E-F(4)、B-E(5)、C-D(6)、F-D(7) 全部跳过（会形成环）。

Prim 算法：贪心扩展 + 优先队列

核心思想

Prim 算法（1957）从一个起始节点出发，逐步”生长”MST：

维护一个”树内”节点集合 $S$ 。每次从割 $\delta(S)$ 中选出最轻边，将新节点纳入 $S$ 。重复直到所有节点都在树内。

这和 Dijkstra 的结构几乎一模一样——区别只在优先队列的排序依据：

Dijkstra：按 $d[v] = d[u] + w(u, v)$ （从源点到 $v$ 的路径长度）
Prim：按 $\text{key}[v] = w(u, v)$ （从 $v$ 到树的最轻边权重）

算法流程

Prim(G, start):
    for each v ∈ V:
        key[v] = ∞
        parent[v] = nil
    key[start] = 0
    PQ = min-priority queue with all v, keyed by key[v]

    while PQ is not empty:
        u = PQ.extract-min()
        for each edge (u, v) with weight w:
            if v ∈ PQ and w < key[v]:   // 注意：是 w，不是 key[u]+w
                key[v] = w
                parent[v] = u
                PQ.decrease-key(v, w)

    return parent (定义了 MST 的边)

与 Dijkstra 的对比

关键区别用一句话概括：Dijkstra 累加路径长度，Prim 只看单条边的权重。Dijkstra 让每个节点到源点的距离最短；Prim 让每个节点到树的连接最便宜。

这个区别导致了不同的结果：Dijkstra 输出最短路径树（SPT，每个节点到源的距离最短），Prim 输出最小生成树（MST，所有边权总和最小）。两棵树通常不同——SPT 优化的是”个体到源的距离”，MST 优化的是”全局连接成本”。

复杂度分析

与 Dijkstra 相同：

优先队列实现	总时间
数组（线性扫描）	$O(V^2)$
二叉堆	$O((V+E)\log V)$
Fibonacci 堆	$O(V\log V + E)$

稠密图（ $E \approx V^2$ ）：数组版 $O(V^2)$ 最优
稀疏图（ $E \approx V$ ）：二叉堆版 $O((V+E)\log V)$ 最实用

Kruskal vs Prim：如何选择？

Kruskal 的瓶颈是排序，不依赖图的结构 → 适合稀疏图（ $m$ 小时排序快）
Prim 的效率取决于优先队列 → 适合稠密图（ $V^2$ 版在稠密图上不比 Kruskal 的 $O(m \log m)$ 差）
Kruskal 天然处理不连通的图（输出最小生成森林），Prim 需要连通图

交互式走查

下面的组件在同一张加权无向图上展示 Kruskal 和 Prim 的完整执行过程。切换算法观察它们的不同策略：Kruskal 全局排序后逐边决策，Prim 从起点贪心扩展。

MST 算法走查

分量数：7

步骤 1/14: Kruskal 初始化：每个节点是独立分量。边按权重排序：C-F(1), A-E(2), D-G(2), B-C(3), F-G(3), A-B(4), E-F(4), B-E(5), C-D(6), F-D(7)

1 / 14

注意关键区别：

Kruskal 按边权从小到大全局处理，并查集判断是否成环
Prim 从 A 出发，每步选”到树最近”的节点加入，用优先队列维护候选

两者在同一张图上输出相同的 MST（权重互不相同时，MST 唯一），但构建顺序不同。

为什么贪心在 MST 上总是有效？拟阵理论的直觉

在最短路径中我们看到：Dijkstra 的贪心在负权边面前失效。为什么 MST 的贪心不会失效？答案来自一个深刻的代数结构——拟阵（Matroid）。

拟阵的定义（直觉版）

拟阵 $(E, \mathcal{I})$ 是一个集合 $E$ （“基础集”）和 $E$ 的子集族 $\mathcal{I}$ （“独立集族”），满足三条公理：

空集独立： $\emptyset \in \mathcal{I}$
遗传性：如果 $B \in \mathcal{I}$ 且 $A \subseteq B$ ，则 $A \in \mathcal{I}$ （独立集的子集也独立）
交换性：如果 $A, B \in \mathcal{I}$ 且 $|A| < |B|$ ，则存在 $b \in B \setminus A$ 使得 $A \cup \{b\} \in \mathcal{I}$

这是对”线性无关”和”无环”概念的统一抽象。拟阵中的极大独立集（无法再扩展的独立集）称为基（basis），所有基的大小相同。

图拟阵（Graphic Matroid）

给定图 $G = (V, E)$ ，定义：

基础集 = $E$ （所有边）
独立集 = $E$ 中不构成环的边集（即森林）

验证三条公理：

空的边集没有环 ✓
森林的子集仍是森林 ✓
较小的森林可以从较大的森林”借”一条边扩展（因为较大的森林连通分量更少，一定有一条边跨越较小森林的某个割）✓

图拟阵的基 = 生成树（恰好 $n - 1$ 条边的连通无环子图）。

贪心在拟阵上的最优性

Rado-Edmonds 定理：对于任意加权拟阵 $(E, \mathcal{I})$ ，以下贪心算法总能找到最小权重的基：

Greedy-Matroid(E, I, w):
    将 E 按权重从小到大排序
    B = ∅
    for each e ∈ E in sorted order:
        if B ∪ {e} ∈ I:  // 加入 e 后仍独立
            B = B ∪ {e}
    return B

将这个定理应用到图拟阵： $E$ = 边集， $\mathcal{I}$ = 无环边集，" $B \cup \{e\} \in \mathcal{I}$ " = “加入 $e$ 不形成环”——这就是 Kruskal 算法！

这就是贪心在 MST 上总有效的根本原因：图的无环边集构成一个拟阵，而贪心在拟阵上一定找到最优基。这不是巧合，是结构性保证。

反过来，当你遇到一个新问题想用贪心时，可以问自己：这个问题的可行解集构成拟阵吗？ 如果是，大胆用贪心；如果不是，贪心可能失败。

Boruvka 算法：并行友好的 MST

核心思想

Boruvka 算法（1926年，是最早的 MST 算法！）的策略天然适合并行：

每一阶段，每个连通分量同时选出它的割中最轻边。所有被选的边加入 MST，对应的分量合并。重复直到只剩一个分量。

算法流程

Boruvka(G):
    MST = ∅
    每个节点初始为独立分量

    while 分量数 > 1:
        for each 分量 C:
            找到 C 的割中最轻边 e_C
        for each 选出的 e_C:
            if e_C 连接两个不同分量:
                MST = MST ∪ {e_C}
                合并对应分量

    return MST

为什么并行友好？

每一阶段中，所有分量独立地选择最轻出边——这些选择互不干扰，可以完全并行。每阶段结束后，分量数至少减半（每个分量至少与另一个合并），因此最多 $O(\log n)$ 阶段。

串行时间： $O(m \log n)$ （每阶段 $O(m)$ 扫描所有边， $O(\log n)$ 阶段）
并行时间： $O(\log^2 n)$ （在 PRAM 模型上，使用 $O(m)$ 个处理器）

Boruvka 是现代并行 MST 算法的基础，在 GPU 和分布式系统上被广泛使用。

复杂度对比

算法	时间复杂度（最坏）	空间	适用场景
Kruskal	$O(m \log m)$	$O(m + n)$	稀疏图；不要求连通
Prim（二叉堆）	$O((n+m)\log n)$	$O(n)$	稠密图；从特定节点出发
Prim（数组）	$O(n^2)$	$O(n)$	稠密图（ $m \approx n^2$ ）
Prim（Fibonacci 堆）	$O(n\log n + m)$	$O(n)$	理论最优（实践常数大）
Boruvka	$O(m \log n)$	$O(m + n)$	并行环境；分布式计算

注：所有复杂度均为最坏情况。当边权互不相同时，MST 唯一；否则可能有多个权重相同的 MST。

选择经验法则：

一般稀疏图 → Kruskal（实现简单，并查集库随处可得）
稠密图 → Prim + 数组（ $O(n^2)$ 在 $m \approx n^2$ 时最优）
需要并行 → Boruvka
竞赛/工程 → Kruskal（代码最短、最不易出错）

Steiner Tree：只连通一部分节点

MST 要求连通所有节点。如果我们只需要连通其中一个子集（称为终端节点，terminal），允许使用其余节点作为中继（Steiner 点）呢？

这就是 Steiner Tree 问题：给定图 $G$ 和终端集合 $R \subseteq V$ ，找一棵连通 $R$ 中所有节点的最小权重树。

P vs NP-hard 的鲜明对比

MST（连通所有节点）：多项式时间 $O(m \log n)$
Steiner Tree（连通指定子集）：NP-hard

差异在哪里？MST 中，“哪些节点要连通”已经确定（全部），算法只需决定”选哪些边”。Steiner Tree 中，还需要决定”经过哪些中继节点”——这个额外的组合选择引入了指数级的搜索空间。

当 $R = V$ 时，Steiner Tree 退化为 MST。当 $|R|$ 很小时，可以用动态规划在 $O(3^{|R|} \cdot n + 2^{|R|} \cdot n^2)$ 时间内精确求解（Dreyfus-Wagner 算法）。一般情况下常用近似算法，其中最简单的一种就是用 MST 近似：

在终端节点的完全图（用原图中的最短路径作为边权）上求 MST。这给出 Steiner Tree 的 2-近似——最坏是最优解的 2 倍。

这是 MST 作为近似算法子程序的一个典型例子。

应用场景

网络布线：最小成本连通

MST 最直接的应用就是网络设计。假设你要用光缆连接 $n$ 个数据中心，任意两个之间铺设光缆的成本已知。MST 给出总成本最低的连接方案。

实际案例：AT&T 的长途电话网络规划在 20 世纪 50 年代就是用 Prim/Kruskal 算法的变种来设计的——这也是 Prim 算法发表在 Bell System Technical Journal 的历史背景。

聚类分析：Single-Linkage Hierarchical Clustering

层次聚类（hierarchical clustering）中最常用的 single-linkage 方法本质上就是 Kruskal 算法的变体：

计算所有数据点之间的距离，构建完全图
运行 Kruskal 算法——每次选最短边时，就是在合并两个最近的簇
Kruskal 执行过程中的合并顺序就是一棵树状图（dendrogram）
在任意高度”切割”树状图，得到不同粒度的聚类

这个等价关系揭示了一个优雅的事实：single-linkage 聚类的树状图恰好由 MST 唯一确定。修改聚类粒度不需要重新计算——只需在 MST 上删除不同的边。

近似算法子程序：TSP 与 Christofides

旅行商问题（TSP）是另一个 NP-hard 问题：找一个经过所有节点恰好一次的最短环路。Christofides 算法（1976）是最著名的 TSP 近似算法，它的第一步就是计算 MST：

计算 MST $T$
找 $T$ 中度为奇数的节点，在它们上做最小权重完美匹配
合并 MST 和匹配，构造欧拉回路
跳过重复节点得到 TSP 近似解

这个算法保证解的质量不超过最优解的 1.5 倍——在 NP-hard 问题上，这是一个极好的保证。MST 在这里提供了 TSP 最优解的下界：任何 TSP 解删掉一条边就是一棵生成树，因此 $\text{MST} \leq \text{OPT}_{TSP}$ 。

图像分割

在计算机视觉中，图像可以建模为图：像素是节点，相邻像素之间有边，边权是颜色/亮度差异。MST 上权重最大的边对应图像中最显著的”边界”——删除这些边就把图像分割成不同的区域。Felzenszwalb & Huttenlocher（2004）的高效图像分割算法正是基于这个思路。

🔁 迭代机器视角 — PrimOPT: 优化目标

Graph	无向加权图
State[v]	key(v) = 到已选集合的最小边权
SELECT	PQ-min（最小权边优先）
COMBINE	扫描邻接边 → 更新 key(v)
重入	无（label-setting）
TERMINATE	Frontier 空（所有节点已选）
求解方法	FI

💡 对比: Dijkstra: 结构完全相同，仅 COMBINE 不同——Dijkstra 用 d(u)+w, Prim 用 w

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

🔁 迭代机器视角 — KruskalOPT: 优化目标

Graph	边列表
State[v]	Union-Find 集合
SELECT	全局排序（边权升序）
COMBINE	Union-Find 检查是否跨越不同分量
TERMINATE	已选 V-1 条边
求解方法	GS

Kruskal 不是 Frontier 迭代——它是贪心扫描 (GS)，按排序后的边列表逐一决策

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

🔁 迭代机器视角 — BorůvkaOPT: 优化目标

Graph	无向加权图 → 逐步收缩
State[v]	分量归属
SELECT	并行——每个分量选最轻出边
COMBINE	合并分量
重入	有界（log V 轮）
TERMINATE	只剩一个分量
求解方法	FI

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

总结

本文开启了 Part 3”优”，从 MST 这个组合优化的经典入门问题出发，建立了以下工具和洞察：

割性质与环性质是 MST 正确性的两个基石——割中最轻边必须选，环中最重边必须弃
Kruskal：全局排序 + 并查集判环， $O(m \log m)$ ，适合稀疏图
Prim：从起点贪心扩展 + 优先队列，结构与 Dijkstra 几乎一样，但松弛的是”到树的距离”而非”到源的距离”
Boruvka：每个分量同时选最轻出边，天然并行， $O(\log n)$ 阶段
拟阵理论：图的无环边集构成拟阵 → 贪心在拟阵上一定最优 → Kruskal 一定正确。这是判断”贪心何时有效”的强大理论框架
Steiner Tree：只连通部分节点 → NP-hard，与 MST 的多项式时间形成鲜明对比
应用：网络布线、层次聚类（single-linkage = Kruskal 变体）、TSP 近似（Christofides 用 MST 做下界）、图像分割

MST 展示了组合优化的第一个主题：贪心策略在正确的结构下可以给出最优解。但大多数组合优化问题没有拟阵结构——贪心会失败。下一篇 Art. 12: 网络流将展示另一种更强大的优化范式——增广路方法：找还能改善的路径，沿路径推进，直到最优。

实现指引

算法	库	函数/方法
MST（默认 Kruskal）	NetworkX	`nx.minimum_spanning_tree(G, algorithm='kruskal')`
MST（Prim）	NetworkX	`nx.minimum_spanning_tree(G, algorithm='prim')`
MST（Boruvka）	NetworkX	`nx.minimum_spanning_tree(G, algorithm='boruvka')`
MST 权重	NetworkX	`nx.minimum_spanning_tree(G).size(weight='weight')`
MST 边列表	NetworkX	`nx.minimum_spanning_edges(G, data=True)`
MST（稀疏矩阵）	scipy	`scipy.sparse.csgraph.minimum_spanning_tree(graph)`
MST	igraph	`g.spanning_tree(weights='weight')`
Steiner Tree（近似）	NetworkX	`nx.algorithms.approximation.steiner_tree(G, terminal_nodes)`