最小生成树

问题定义#

给定一个连通的无向加权图 $G = (V, E, w)$，其中： - $V$ 是顶点集（城市、服务器、神经元……） - $E$ 是边集（连接关系） - $w: E \to \mathbb{R}$ 是边的权重函数（距离、成本、延迟……）

生成树（Spanning Tree）是图 G 的一个子图，满足： 1. 包含 G 的所有顶点 2. 是连通的 3. 是无环的（树）

一棵 $n$ 个顶点的生成树有且仅有 $n-1$ 条边。

最小生成树（Minimum Spanning Tree，MST）是所有生成树中，边权之和最小的那棵（或几棵——可能有多棵权值相同的 MST）。

生成树数量可以是天文数字（完备图上由 Cayley 公式给出 $n^{n-2}$ 棵不同的树），因此"枚举再取最小"在算法上不可行。MST 问题的精妙之处在于：尽管候选解空间巨大，却存在多项式时间的贪心结构——切割引理与环性质共同保证了局部最优选择可以拼出全局最优。

问题边界还常与斯坦纳树缠在一起：后者允许额外引入斯坦纳点来缩短总长，MST 则不许加点，候选边必须来自给定图。一旦放开插入点，问题立即进入 NP 难。工程上若"布线最短"允许中继站或会合点，问的已不是 MST。无向连通、顶点集锁定、边权事先给定——三条同时成立，才轮到 Kruskal 或 Prim；缺任何一条应先改问题陈述，而不是改堆的实现。

破除误解：MST 不是"最短路径树"#

MST 是总权重最小的树，但它不保证任意两点之间的路径最短。最短路径树（以某个点为根，到所有其他点路径最短）是不同的概念：

例子：4 个顶点的图
A ——5—— B
|        |
1        3
|        |
C ——2—— D

MST 使用的边：A-C(1), C-D(2), B-D(3)，总权重=6
A 到 B 的路径通过 MST：A→C→D→B，长度=6
A 到 B 的最短路径：A→B，长度=5（MST 中不含此边！）

MST 连接所有节点的总成本最低，但不保证通信路径最短——两者是不同的优化目标。

Kruskal 算法：从小到大，贪心加边#

1956 年，约瑟夫·伯纳德·克鲁斯卡尔（Joseph Bernard Kruskal, Jr.）发表了 Kruskal 算法：

思路：按边的权重从小到大排序。逐条取出最小权重的边，如果加入这条边不形成环，就把它加入 MST；否则跳过。重复直到 MST 有 $n-1$ 条边。

def kruskal(vertices, edges):
    # 1. 按权重排序所有边
    edges.sort(key=lambda e: e.weight)
    
    # 2. 并查集：用于高效判断是否成环
    uf = UnionFind(vertices)
    mst = []
    
    for edge in edges:
        u, v, w = edge.u, edge.v, edge.weight
        # 如果 u 和 v 不在同一连通分量，加这条边不会形成环
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append(edge)
            if len(mst) == len(vertices) - 1:
                break  # MST 已完成
    
    return mst

关键数据结构：并查集（Union-Find）

判断两个顶点是否已连通（即加边是否会形成环），需要高效的数据结构。并查集（Disjoint Set Union，DSU）支持两种操作： - find(x)：找到 x 所在连通分量的代表元 - union(x, y)：合并 x 和 y 所在的连通分量

通过路径压缩（Path Compression）和按秩合并（Union by Rank），每次操作的均摊时间复杂度接近 $O(\alpha(n))$（反阿克曼函数，增长极慢，实践中视为常数）。

Kruskal 的总时间复杂度由排序步骤主导：$O(E \log E)$（对稀疏图非常高效）。并查集几乎"免费"这一事实，常被用来反衬：MST 的算法瓶颈往往不在连通性查询，而在如何廉价地获得边的相对顺序或最轻出边。边权若来自外部已排序流，Kruskal 可接近线性；若图极稠密，把注意力转到 Prim 的 $O(V^2)$ 扫描往往更划算。

贪心正确性证明#

为什么贪心选择（每次选最小的不成环的边）是正确的？

切割引理（Cut Property）：对于图 G 的任意一个"切割"（把顶点集分成两部分的划分），连接两部分的权重最小的边一定属于某棵 MST。

证明直觉：假设 MST 不包含某个切割的最小边 $e^*$，而 MST 中连接这个切割的边是 $e'$（权重 $>$ $e^*$ 的权重）。那么把 $e^*$ 换入、把 $e'$ 移出，总权重下降——与 MST 的最优性矛盾。

Kruskal 的每次加边都满足切割引理：当前最轻且不成环的边，其两端分属两个连通分量，这条边恰是"该分量 vs 其余"这类切割上的最轻跨越边之一。

对称的还有环性质（Cycle Property）：任取图中一个环，环上权重最大的边一定不属于任何 MST（若所有边权互异，则不属于唯一的那棵）。Kruskal 跳过成环边，等价于拒绝把环上的"多余边"留下；反向删除算法（从密到疏删最重边）则直接执行环性质。切割引理负责"必须留下什么"，环性质负责"必须丢掉什么"——两者是同一最优性结构的两面。

Prim 算法：从一点出发，逐步生长#

1957 年，罗伯特·克莱·普里姆（Robert Clay Prim）发表了 Prim 算法（迪科斯彻于 1959 年又独立重新发现，更早的版本则由捷克数学家雅尔尼克于 1930 年给出，因此该算法也称 Jarník–Prim 或 DJP 算法）：

思路：从任意一个顶点出发，维护"已加入 MST 的顶点集 S"。每次找到一条连接 S 内顶点和 S 外顶点的最小权重边，把对应的 S 外顶点加入 S。重复 $n-1$ 次。

def prim(graph, start):
    n = len(graph)
    in_mst = {start}
    key = {v: float('inf') for v in graph}  # 加入 MST 的最小代价
    key[start] = 0
    parent = {v: None for v in graph}
    mst_edges = []
    
    import heapq
    pq = [(0, start)]  # (边权, 顶点)
    
    while pq and len(in_mst) < n:
        w, u = heapq.heappop(pq)
        if u in in_mst and u != start:
            continue
        in_mst.add(u)
        if parent[u] is not None:
            mst_edges.append((parent[u], u, w))
        
        for v, weight in graph[u]:
            if v not in in_mst and weight < key[v]:
                key[v] = weight
                parent[v] = u
                heapq.heappush(pq, (weight, v))
    
    return mst_edges

Prim 算法与 Dijkstra 算法结构非常相似——都是从一个起点"贪心"地扩展。区别在于： - Dijkstra：每次选距起点路径总长度最小的顶点 - Prim：每次选连接 MST 的边权最小的顶点

用二叉堆实现，Prim 的复杂度是 $O((V + E) \log V)$；用斐波那契堆可降至 $O(E + V \log V)$（Fredman-Tarjan，1987，见文末"线性时间的悬案"）；对稠密图（$E \approx V^2$），朴素实现（直接遍历找最小 key）的复杂度 $O(V^2)$ 反而更优——稠密图上堆的每次操作都是纯 overhead，直接扫数组还更省常数。

实现细节常被低估：key[v] 记录的是"把 v 接到当前树的最便宜边权"，不是到起点的距离；松弛成功时更新的是跨越边，而不是路径累加。把 Prim 的优先队列键误写成 Dijkstra 式的路径长，会悄悄解成另一棵树——这是教学与工程中最常见的串味错误。边权可为零或负数时 MST 仍良定义（与最短路不同），因为目标是边权和而非路径可达代价。

还有一个常被作业漏写的前提：输入必须是无向图。有向图上的最小树形图（Chu–Liu / Edmonds 的 optimum branching）要处理入度约束与环收缩，并不能把并查集原样搬过去。把有向通信网交给 Prim，会在根的选择与反向弧上静默失败。Prim 与 Dijkstra 代码长得像，并不等于问题域可互换：一个求无向骨架，一个求单源可达代价；堆键写错只是串味的一种，把有向性忽略则是另一种。

一条定理，三种算法#

回头看，Kruskal、Prim 和 Borůvka 并不是三个算法，而是切割引理的三种调度方式。

切割引理说：任意把顶点切成两半，跨越切口的最轻边必属于某棵 MST。三个算法的全部区别，在于每一轮选择哪些切口：

• Prim 每步只用一个切口：已长成的树 vs 其余顶点。切口随树的生长不断推移，像墨水在图上洇开。
• Kruskal 每步由当前最轻边两端的连通分量隐含定义切口：全局排序保证"最轻的未成环边"必然是某个切口的最轻边。切口是局部的、跳跃的，由排序顺序驱动。
• Borůvka（见后文）每轮同时取所有连通分量的切口：每个分量各自选出最轻出边，一次性全部加入。

同一个正确性理由，三种并发度。这个视角也解释了为什么改换调度不改变结果的本质——只要每一步都满足切割引理，拼出来的必然是某棵 MST。

若边权不全互异，"某棵"可以变成"某一族"。算法仍正确，但输出依赖于平局打破规则：Kruskal 看排序稳定性与边序号，Prim 看堆中顶点弹出次序，Borůvka 看各分量选边时的比较器。工程上若需要可复现的拓扑（例如生成测试夹具或确定性网络配置），必须显式规定平局键，而不能假定"MST"一词自动唯一。

两种算法的适用场景#

Borůvka 算法：并行天生#

博鲁夫卡 1926 年的算法在今天的大规模图处理中重新获得关注，因为它天然并行：

思路：每轮，每个连通分量同时找从本分量出发的最小权重边，把对应的连通分量合并。每轮合并后，连通分量数量至少减半（每个分量至少选出一条出边，一条边至多合并两个分量）。因此至多 $O(\log V)$ 轮后，所有顶点合并为一个连通分量（即 MST 完成）。

并行的关键在于每轮的工作是完全局部的：每个分量只检查自己的出边，不需要知道其他分量在做什么，没有中心瓶颈；轮与轮之间的一次全局同步（给新分量重新标号）是唯一的协调点，而轮数只有对数级。这与 Kruskal 形成鲜明对照——Kruskal 的第 $i$ 条边能否加入依赖前 $i-1$ 条边的处理结果，本质串行。

这正是 MapReduce 一类框架的理想形状：一轮 Map（各分量找最小出边）加一轮 Reduce（合并分量）恰好对应 Borůvka 的一轮，对数轮迭代即收敛。Google 和 Facebook 的大规模图分析系统都使用了类 Borůvka 的方法。

实现时有两个算法细节值得单独拎出。其一是平局：若两个分量互相把对方选为最轻出边，必须用确定性规则（边 ID、端点序）只保留一条，否则会引入环。其二是收缩：每轮把新连通分量压成超点后，平行边只保留最轻者，图规模随轮次指数下降。Borůvka 也常作为其他算法的预处理——先收缩若干轮，再把残图交给 Kruskal 或随机采样步骤，这正是接近线性时间算法的常用拼装方式。

MST 的应用#

网络规划：用最小代价连接所有节点——通信网络、输电网络、管道网络的布线规划。实际工程很少停在纯 MST：无环意味着单点故障即分裂，因此常在 MST 骨架上再加备份边，或改用有度约束、容量约束的变体。算法课上的最优树，是可靠性设计的下界参照，而不是施工图的终稿。

图像分割：Felzenszwalb-Huttenlocher 算法（2004）基于 MST 的思想，把图像像素作为图的顶点，相邻像素之间的颜色差异作为边权，用类似 MST 的方法把图像分割成语义区域。这是计算机视觉领域的经典算法之一。

聚类算法：把 MST 的最重的 k-1 条边删掉，得到 k 个连通分量，这是一种层次聚类方法（Single-Linkage Clustering）。对异形状的簇（非球形），这种方法比 K-means 更有效。

近似算法：最小权重哈密顿回路（度量 TSP）是 NP 难的，但 MST 给出经典 2-近似：先求 MST，沿树做深度优先遍历并 shortcut 重复顶点，得到的回路长度至多两倍于最优。证明骨架是：最优回路删一边得生成路径，其权重 ≥ MST；DFS 遍历每条树边至多走两次。Christofides 算法在此基础上加入最小权完美匹配，把保证比改进到 1.5——仍以 MST 为骨架。

树协议（Spanning Tree Protocol，STP）：以太网交换机之间通过 STP 自动构建一棵生成树，防止网络环路。802.1D 标准（1990）正是 MST 思想在网络协议中的直接应用。协议层的"权重"常由链路带宽与桥优先级合成，目标同样是无环连通，只是优化准则换成了工程度量。

代价与争议#

唯一性：若所有边权都不同，MST 唯一。若有相同边权，MST 可能有多棵。这在某些应用场景（如需要确定性的网络协议）中需要额外的决策规则（如按顶点 ID 打破平局）。

线性时间的悬案：Kruskal 和 Prim 都是 $O(E \log E)$ 或 $O(E \log V)$。一个长期开放的问题是：是否存在确定性的 $O(E)$ 算法？比较模型下，若边权是任意实数，排序下界似乎挡在门外；但 MST 并不需要全排序——它只需要足够多的"相对顺序"来决定去留，于是真正的问题变成：决策树需要探询多少次比较。

目前已知：弗雷德曼-塔扬（Fredman-Tarjan，1987）用斐波那契堆实现了 $O(E + V \log V)$；卡格-克莱因-塔扬（Karger-Klein-Tarjan，1995）给出了随机化的 $O(E)$ 期望时间算法；夏泽勒（Chazelle，2000）用软堆（soft heap）给出了确定性的 $O(E\,\alpha(E,V))$ 算法（反阿克曼级别，已极接近线性）；彼得森-拉马钱德兰（Pettie-Ramachandran，2002）给出了"可证明最优"的确定性算法——其运行时间恰好等于 MST 问题本身的决策树复杂度，但这个复杂度的精确量级至今没人知道（连它是不是 $\Theta(E)$ 都未确定）。因此，确定性 $O(E)$ MST 算法是否存在，至今是开放问题。

Karger-Klein-Tarjan 那条"随机化线性"的思路值得展开，因为它把本文的几样东西串了起来。第一步，先跑若干轮 Borůvka，把顶点数收缩到一个零头。第二步，对剩下的边随机采样一半，递归求出采样子图的 MST。第三步，用这棵"采样 MST"当筛子：原图中若某条边比采样树上对应路径的最重边还重，它与该路径构成的环上它就是最重边——由环性质（环上的最重边不属于任何 MST），它绝不可能出现在原图的 MST 中，直接删除。可以证明筛完后剩下的边期望只有线性条，再递归一次即可。随机采样在这里的作用不是近似答案，而是廉价地获得一个"足够好的筛子"，把确定无用的边成批剪掉。

验证构成对照：给定一棵生成树，判断它是不是 MST，已有近线性甚至线性时间的算法。构造仍可能卡在比较次数的下界，验证却适合当测试夹具——随机扰动边权再对照输出，比对着示意图目测更可靠。开放问题因此不是"如何确认一棵候选"，而是"如何在不够多次比较时把那棵树找出来"。

跨域连接#

• 并查集：判定加边是否成环等价于判定两点是否已连通，路径压缩加按秩合并把每次操作压到近乎常数——增长极慢的反阿克曼级别。排序因此成为真正的瓶颈，边权若已排好序，整个算法接近线性。这是"选对辅助结构比优化主循环更值钱"的标准案例。
• 网络科学：它是网络的骨架，删掉最重的若干条边就得到层次聚类，这与逐步降低连接阈值、观察连通块如何合并是同一个过程。它同时暴露了单连接聚类的病：两个簇之间只要存在一串中间点就会被连成一个，因为判据只看最小的那条边。链式效应不是实现缺陷，是定义的直接后果。
• Dijkstra 最短路径：Prim 与 Dijkstra 结构几乎相同，都是反复取"当前最便宜的下一个节点"，区别只在键的定义：一个是跨越边的权重，一个是到源点的累计距离。后果是两棵树不同，生成树里任意两点的路径可以远长于它们的最短路。把布线成本最低误当成通信延迟最低，是网络规划里常见的错。
• 流行病学：从病原体基因组的两两差异构建最小生成树来推断传播链，是暴发调查的常规做法。但算法必然输出一棵树，哪怕真实情况是多次独立引入。树是被算法造出来的结构，不是数据里现成的证据，所以结论必须与接触史交叉验证；差异矩阵里若存在多棵几乎等价的最小树，那本身就是"链条不可靠"的信号。
• 共有资源治理：共同建设的灌溉渠、电网或道路，最小总成本容易算，难的是谁付多少。这里只回答前者；后者是合作博弈问题——分摊方案必须让任何子集都不愿脱离另建，否则联盟瓦解。这也解释了工程上为何很少真按最小生成树建：无环意味着零冗余，断一条边网络就分裂，而可靠性要求必须额外加边。

参考文献#

• Kruskal, J. B. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the AMS 7(1), 1956.
• Prim, R. C. Shortest Connection Networks and Some Generalizations. Bell System Technical Journal 36(6), 1957.
• Borůvka, O. O jistém problému minimálním (On a minimal problem). Práce Mor. Přírodověd. Spol. v Brně 3, 1926.
• Cormen, T. et al. Introduction to Algorithms (CLRS). 3rd ed. 第 23 章. MIT Press, 2009.

延伸阅读#

• Graham, R. L. & Hell, P. On the History of the Minimum Spanning Tree Problem. IEEE Annals of the History of Computing 7(1), 1985.（MST 历史的权威综述）