Prim 最小生成树算法详解

Mohammed Islam Hadjoudj

资深运筹学工程师

1. Prim 算法简介

Prim 算法用于构造最小生成树：给定一个连通的无向带权图，它挑选出一组边，使之覆盖所有顶点、不含任何环，且总权重尽可能小。对于有 V 个顶点的图，这组边恰好总是 V - 1 条。

它的策略是让一棵树向外生长。从任意顶点出发，反复越过已建部分的边界，把触及某个尚未纳入的顶点的最便宜的边拉进来。重复 V - 1 次，树便完成了。整个过程没有回溯，也从不删除任何东西。

这个描述听起来贪心得几乎不可能正确。只挑当下最便宜的边、完全不向前看，正是最短路径问题中一旦出现负权边就会失败的策略。但对最小生成树而言它不会失败，原因是一条定理，值得在动手写代码之前先弄懂。

2. 为什么它是对的：割性质

割把顶点分成两个非空的组。若一条边的两个端点落在不同组中，就称它横跨该割。支撑 Prim 算法的定理如下：

证明很短，也值得一看，因为它解释了整个算法。设 e 是横跨某个割的最便宜的边，并假设某棵最小生成树 T 不含它。把 e 加入 T 恰好会形成一个环，而这个环必然会第二次横跨该割，用到另一条边 f。删掉 f。你手上仍是一棵生成树，而由于 e 是最便宜的横跨边，其权重不大于 f，因此新树不会更重。于是必定存在一棵包含 e 的最小生成树。

现在看 Prim 算法每一步在做什么。已在树中的顶点构成割的一侧，其余顶点构成另一侧。算法选取的正是横跨这个割的最便宜的边。根据割性质，它选出的每条边都是安全的：都属于某棵最小生成树。这种贪心选择从来不是碰巧奏效的赌博，而是被应用了 V - 1 次的定理。

3. 树是如何生长的

具体来说，算法维护三样东西：已在树中的顶点集合、树外每个顶点的 key 值，以及记录该键由哪个树内顶点提供的 parent 指针。

• key[v] 是把 v 连到当前树上的最便宜的单条边的权重；若尚不存在这样的边，则为无穷大。
• parent[v] 是该边另一端的树内顶点。正是它让你在结束时能输出真正的树，而不只是树的权重。

每一轮取出树外 key 最小的顶点，连同通往其 parent 的那条边一起加入，然后进行松弛：对每个仍在树外的邻居 w，若通往 w 的边比 key[w] 更便宜，就下调 key[w] 并改写 parent[w]。

请特别注意键代表什么。它是一条边的权重，而不是一条路径的代价。正是这个细节把本算法与 Dijkstra 算法区分开来，等代码写出来之后我们会回到这一点。

4. 逐步执行演示

取我们最小生成树指南中一直使用的那个六顶点图。它的九条边是：

A-B 4    A-C 1    B-C 2
B-D 5    C-D 6    C-E 7
D-E 2    D-F 8    E-F 3

从 A 开始。每一轮中，“前沿”是恰好有一个端点在树内的那些边，算法从中取最便宜的一条。

1. 树 = {A}。前沿：A-C（1）、A-B（4）。最便宜的是 A-C（1）。加入 C。
2. 树 = {A, C}。前沿：B-C（2）、A-B（4）、C-D（6）、C-E（7）。注意 B 现在有两条路可达，经 A 为 4、经 C 为 2，因此它的键降为 2。最便宜的是 B-C（2）。加入 B。
3. 树 = {A, C, B}。前沿：B-D（5）、C-D（6）、C-E（7）。D 可经 5 或 6 到达，故其键为 5。最便宜的是 B-D（5）。加入 D。
4. 树 = {A, C, B, D}。前沿：D-E（2）、C-E（7）、D-F（8）。E 的键由 7 降到 2。最便宜的是 D-E（2）。加入 E。
5. 树 = {A, C, B, D, E}。前沿：E-F（3）、D-F（8）。F 的键由 8 降到 3。最便宜的是 E-F（3）。加入 F。

六个顶点加了五条边，算法随即停止。这棵树由 A-C（1）、B-C（2）、B-D（5）、D-E（2）、E-F（3）组成，总权重为 13。边 A-B（4）、C-D（6）、C-E（7）与 D-F（8）始终未被使用。

这段执行过程中有两处值得停下来体会。第 3 轮里，算法接受了一条权重为 5 的边，而此时图中别处还躺着一条权重为 2 的边（D-E）无人问津。Prim 之所以还不能取 D-E，是因为它的两个端点都不在树中，取了只会留下两个互不相连的碎片，而非一棵不断生长的树。第 4 轮中，D 一加入，E 的键便从 7 降到 2。键只会变小，而这正是优先队列实现之所以高效的原因。

5. 实现：惰性与主动两种 Prim

常见的实现有两种，差别在于优先队列里装的是什么。

惰性 Prim

较简单的版本把遇到的每一条边都压入最小堆，等弹出时再丢弃那些已经失效的条目。

function LazyPrim(Graph, start):
    inTree = set()
    pq = 空的最小堆，按边权排序
    mst = []

    visit(start)                    // 标记它并压入其所有边

    while pq 非空 and size(mst) < V - 1:
        (w, u, v) = pq.pop()        // 目前见过的最便宜的边
        if v in inTree: continue    // 已失效：两端都已在树中
        mst.append((u, v, w))
        visit(v)

    return mst

function visit(x):
    inTree.add(x)
    for 每条边 (x, y)，权重为 w:
        if y not in inTree: pq.push((w, x, y))

真正干活的是 if v in inTree: continue 这一行。它防止成环，也正因为有它，堆里可以安全地留着过时的条目：它们浮上来时直接跳过即可。

主动 Prim

主动版本对每个顶点最多只保留一个条目，即当前的 key[v]，并用 decrease-key 操作就地下调。它需要一个带索引的优先队列，机制更复杂，但堆的规模永远不超过 V 个条目，而不是 E 个。

function EagerPrim(Graph, start):
    for 每个顶点 v:
        key[v] = Infinity
        parent[v] = Null
    key[start] = 0
    pq = 所有顶点构成的带索引最小堆，按 key[] 排序

    while pq 非空:
        u = pq.popMin()
        inTree.add(u)
        for 每条边 (u, v)，权重为 w:
            if v not in inTree and w < key[v]:
                key[v] = w                  // 是边权，不是累加和
                parent[v] = u
                pq.decreaseKey(v, w)

    return parent            // parent[] 就是这棵树

在稠密图上优先选用主动 Prim，因为此时 E 远大于 V，把每条边都塞进堆里非常浪费。在稀疏图上，惰性 Prim 完全够用，而且写对它要容易得多。

6. 时间与空间复杂度

• 惰性 Prim，二叉堆：时间 O(E log E)。每条边最多入堆一次、出堆一次。由于 E < V2，log E 属于 O(log V)，因此通常写作 O(E log V)。空间为 O(E)。
• 主动 Prim，带索引二叉堆：时间 O(E log V)，来自 V 次弹出与至多 E 次 decrease-key，每次 O(log V)。空间为 O(V)。
• 主动 Prim，不用堆、改用邻接矩阵：线性扫描找最小键，时间 O(V2)。在 E 接近 V2 的稠密图上，它优于堆版本，因为 O(V2) 好过 O(V2 log V)。
• 主动 Prim，斐波那契堆：O(E + V log V)，是 Prim 已知的最佳界，因为 decrease-key 变为均摊常数时间。但其常数因子较大，实际中很少胜出。

实用结论：稀疏图用二叉堆，稠密图用朴素的 O(V2) 矩阵扫描。斐波那契堆主要具有理论意义。

7. Prim 与 Dijkstra：只差一行

把主动 Prim 的伪代码与 Dijkstra 算法并排放着看，它们几乎是同一个程序。两者都为每个顶点维护一个键，都反复取出最小值，都对刚取出顶点的邻居做松弛。全部差别只在于键里放的是什么：

Prim:      if w < key[v]:              key[v] = w
Dijkstra:  if key[u] + w < key[v]:     key[v] = key[u] + w

Prim 的键是单条边的权重，Dijkstra 的键是从源点出发整条路径的累计长度。这正是二者回答的问题不同的原因：Prim 问的是“把这个顶点挂到我的树上，最便宜要多少”，而 Dijkstra 问的是“从源点抵达这个顶点，最便宜要多少”。

这也解释了为什么负权重会击垮其中一个而不影响另一个。Dijkstra 的正确性依赖于路径变长时代价不会变小，而负权边正好摧毁这一点。Prim 从不把权重相加，所以负权边对它完全无害。在带负权的图上，最小生成树依然是良定义的，Prim 无需任何修改即可求出它。

8. Prim 与 Kruskal

两个算法都是贪心的，都由割性质提供依据，在边权互不相同的图上两者返回完全相同的树。它们的差别在于过程中保持连通的是什么。

• Prim 始终维护一棵连通的树并让它向外生长。它从不排序边，但需要一个优先队列。
• Kruskal 把所有边按权重排序，逐条加入，除非会形成环，因此它维护的是一片由碎片组成的森林，直到最后才合并成一棵树。它需要并查集结构。

实用准则由稠密程度决定。Kruskal 的开销由排序主导，为 O(E log E)，在 E 较小时非常出色。Prim 配合邻接矩阵，无论边数多少都是 O(V2)，在稠密图上更占优。面对非连通输入还有一个结构性差异：Kruskal 天然产出最小生成森林，而从单个起点出发的 Prim 只能覆盖该顶点所在的连通分量，因此每个分量都必须重新启动一次。

9. 实践要点与常见陷阱

从教科书情形走向真实输入时，有四种情况最容易出问题。

• 权重相同意味着答案不止一个。当两条边权重相等时，图可能拥有不止一棵最小生成树，你得到哪一棵取决于优先队列如何打破平局。它们同样最优，因此拿硬编码的边列表去比对的测试会毫无道理地失败。应当改为比较总权重。
• 非连通输入会悄无声息地出错。从某个顶点启动时，Prim 只覆盖该顶点所在的分量便停止，返回的树看上去完全合法。检查办法是计数：真正的生成树恰有 V - 1 条边。少于此数就说明图是非连通的，需要从一个尚未访问的顶点重新启动。
• 自环与重边。自环永远无法横跨任何割，因此总可忽略。连接同一对顶点的多条重边中，只有最便宜的那条可能被选中。两者都不会破坏算法，但在读入时就过滤掉可以让堆更小。
• 有向图是完全不同的问题。最小生成树是针对无向图定义的。把有向边喂给 Prim 得到的结果没有意义。其有向对应物是最小生成树形图，由 Edmonds 算法求解，难度也高得多。

10. 变体与实际应用

最小生成树回答的是一个反复出现的问题：把所有节点连起来、且不留冗余，最便宜的方案是什么？Prim 适合网络确实从某个源头生长出来的场景。

管网与线路铺设

在一组固定站点之间铺设电缆、光纤、水管或道路，要求每个站点都可达，并以总长度或总成本为最小化目标，这正是最初的动机。Prim 的论文就是在贝尔实验室处理这一问题时产生的。

聚类分析

先求点集的最小生成树，再删去其中最重的若干条边，就是单连接聚类：删掉最重的 k - 1 条边，恰好剩下 k 个簇。树只需计算一次，任意 k 值都能由它直接得出。

更难问题的近似

最小生成树为旅行商回路给出了下界，把它的边加倍即可在度量实例上得到一条不超过最优解两倍的回路。它也是 Christofides 构造的起点，后者把这一保证改进到 1.5。

图像分割与迷宫生成

把像素视为顶点、把差异度视为边权，基于最小生成树的分割便能把图像划分成若干区域。若改为在带随机权重的网格上运行 Prim，则会得到风格均匀的迷宫，这也是它成为程序化生成常用手法的原因。

11. 学术资源与历史

与若干经典图算法一样，这个算法被不止一次地发现，而它所冠的名字并不属于最早发现它的人。

• Otakar Borůvka（1926）最早提出并解决了最小生成树问题，动机是为摩拉维亚乡村通电。他的算法是另一种：在并行的若干轮中，为每个碎片各加入一条最便宜的出边。
• Vojtěch Jarník（1930）在回复 Borůvka 的一封信中发表了我们今天称为 Prim 的算法。因此把它称作 Jarník-Prim 算法其实更为准确。
• Robert C. Prim（1957）在贝尔实验室研究连接网络成本时独立地重新发现了它，而正是他的论文让这一算法广为人知。
• Edsger W. Dijkstra（1959）第三次独立发现了它，就写在那篇引入他最短路径算法的短文里；考虑到两者何其相近，这并非巧合。

关于谁在何时发现了什么，权威梳理见 Graham 与 Hell 所写的问题史。若需要附有割性质与两个算法完整证明的严谨论述，标准参考书是 Cormen、Leiserson、Rivest 与 Stein 合著的 Introduction to Algorithms 中关于最小生成树的一章。想了解复杂度被推进到何种程度的读者，还应参阅 Fredman 与 Tarjan 的斐波那契堆成果，以及 Chazelle 的近线性算法。完整文献信息列于本文末尾。