Prim’s Algorithm：最小生成树

一句话概括

Prim 算法从任意起点出发，维护一棵不断扩张的树；每一步选择连接”树内顶点”和”树外顶点”的最小权重边，直到所有顶点都被纳入。

目录

• 1. 问题定义

• 2. 基本思想

• 3. 具体过程

• 4. 正确性依据

• 5. 伪代码

• 6. 时空间复杂度

• 7. 问题需要具有的性质

• 8. 典型例子

• 9. 常见错误

• 10. 与 Kruskal 算法的对比

1. 问题定义

给定一个带权无向图：

$$G=(V,E),\qquad w:E\rightarrow \mathbb{R}$$

生成树 $T$ 需要满足：

1. 覆盖图中的全部顶点；

2. 连通；

3. 不含环；

4. 恰好包含 $|V|-1$ 条边。

最小生成树（Minimum Spanning Tree, MST）要求生成树的总权重最小：

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

生成树与最短路径树不同

• 最小生成树最小化的是整棵树的边权总和。

• 最短路径树最小化的是指定源点到各顶点的路径长度。

• 因此，Prim 算法不能替代 Dijkstra’s Algorithm。

2. 基本思想

Prim 算法是一种贪心算法。

设：

• $S$：已经加入生成树的顶点集合；

• $V-S$：尚未加入生成树的顶点集合；

• $T$：当前已经选择的边集合。

每一步都在所有跨越割 $(S,V-S)$ 的边中，选择权重最小的一条边：

$$(u,v)=\arg\min \left\{ w(x,y)\mid x\in S,\ y\in V-S \right\}$$

然后：

• 将边 (u,v) 加入 $T$；

• 将顶点 v 加入 $S$。

当 $S=V$ 时，$T$ 就是一棵最小生成树。

核心不变量

在算法执行的任意时刻：

1. $T$ 始终是一棵树，不会形成环；

2. $T$ 始终可以扩展为某一棵最小生成树；

3. 下一条加入的边必须连接 $S$ 与 $V-S$。

3. 具体过程

3.1 维护的信息

对每个尚未加入生成树的顶点 v，维护：

• key[v]：当前从 $S$ 连接到 v 的最小边权；

• parent[v]：使 key[v] 取得最小值的树内顶点。

初始化时选择任意起点 r：

$$key[r]=0$$

其他顶点：

$$key[v]=+\infty,\qquad v\ne r$$

3.2 每轮操作

重复以下过程，直到优先队列为空：

1. 从尚未加入生成树的顶点中，取出 key 最小的顶点 u；

2. 将 u 加入集合 $S$；

3. 若 u 不是起点，则将边 (parent[u],u) 加入最小生成树；

4. 检查 u 的所有邻接点 v：

   • 若 $v\notin S$；

   • 并且 $w(u,v)<\mathrm{key}[v]$；

   • 则更新：

$$key[v]\leftarrow w(u,v)$$ $$parent[v]\leftarrow u$$

该更新过程本质上是用新加入的顶点 u，尝试为树外顶点找到更便宜的连接边。

3.3 状态变化示意

4. 正确性依据

Prim 算法的正确性依赖最小生成树的割性质（cut property）。

割性质

假设边集合 A 已经包含在某棵最小生成树中。对于任意一个尊重 A 的割 $(S,V-S)$，跨越该割的最轻边都是相对于 A 的安全边，可以加入而不破坏最优性。

Prim 算法中：

• 当前树内顶点构成集合 $S$；

• 当前树外顶点构成集合 $V-S$；

• 已选边全部位于 $S$ 内，因此割 $(S,V-S)$ 尊重已选边集合；

• 算法选择跨越该割的最轻边。

所以，每一次贪心选择都是安全的。持续加入安全边，最终得到包含 $|V|-1$ 条边的最小生成树。

4.1 交换论证直觉

假设 Prim 选择了跨越割的最轻边 e，但某棵最小生成树 $T^*$ 不包含 e：

1. 将 e 加入 $T^*$，会形成一个环；

2. 该环中一定存在另一条同样跨越该割的边 f；

3. 因为 e 是跨越该割的最轻边，所以：

$$w(e)\leq w(f)$$

4. 删除 f，保留 e，仍然得到一棵生成树；

5. 新生成树的权重不大于 $T^*$。

因此，存在一棵包含 e 的最小生成树，说明选择 e 是安全的。

5. 伪代码

下面采用邻接表 + 最小优先队列实现。优先队列按 key[v] 从小到大排列。

PRIM(G, w, r):  
    for each vertex v in G.V:  
        key[v] <- +infinity  
        parent[v] <- NIL  
        inMST[v] <- false  
​  
    key[r] <- 0  
    Q <- minimum-priority-queue containing all vertices  
​  
    while Q is not empty:  
        u <- EXTRACT-MIN(Q)  
        inMST[u] <- true  
​  
        for each edge (u, v) in G.Adj[u]:  
            if inMST[v] = false and w(u, v) < key[v]:  
                parent[v] <- u  
                key[v] <- w(u, v)  
                DECREASE-KEY(Q, v, key[v])  
​  
    T <- empty set  
    for each vertex v in G.V - {r}:  
        T <- T union {(parent[v], v)}  
​  
    return T

实现时的两种写法

• Eager Prim：每个顶点在优先队列中保留一份记录，更新时执行 DECREASE-KEY。

• Lazy Prim：发现候选边时直接压入堆，取出时跳过已经访问的顶点；实现更简单，但堆中可能存在过期记录。

6. 时空间复杂度

设：

• 顶点数为 $|V|$；

• 边数为 $|E|$。

6.1 邻接矩阵实现

每轮在线性时间内寻找 key 最小的树外顶点，共执行 $|V|$ 轮：

$$T(V,E)=O(V^2)$$

空间复杂度：

$$O(V^2)$$

适合稠密图。

6.2 邻接表 + 二叉最小堆

• EXTRACT-MIN：执行 $|V|$ 次，每次 $O(\log V)$；

• 每条边至多触发一次有效更新，DECREASE-KEY 为 $O(\log V)$。

因此：

$$T(V,E)=O((V+E)\log V)$$

连通图满足 $E\geq V-1$，通常写为：

$$\boxed{O(E\log V)}$$

空间复杂度：

$$\boxed{O(V+E)}$$

适合稀疏图。

6.3 使用 Fibonacci 堆

理论上可以达到：

$$O(E+V\log V)$$

但实现复杂，工程中通常使用二叉堆。

7. 问题需要具有的性质

7.1 必要输入条件

Prim 算法直接求解的是：

适用问题

连通、带权、无向图的最小生成树问题。

具体要求如下：

1. 无向图

   • Prim 的割性质针对无向图的生成树。

   • 有向图中的对应问题是最小树形图（minimum arborescence），需要其他算法。

2. 图是连通的

   • 只有连通图才存在覆盖全部顶点的生成树。

   • 若图不连通，分别对每个连通分量运行 Prim，得到的是最小生成森林（minimum spanning forest）。

3. 边具有可比较的权重

   • 算法必须能够判断候选边中哪条更轻。

7.2 不需要满足的条件

Prim 算法不要求：

• 边权必须为正数；

• 边权必须非负；

• 所有边权互不相同；

• 图必须是稀疏图；

• 起点必须是某个特殊顶点。

关于负权边

Prim 算法可以处理负权边，因为它比较的是跨越当前割的边权大小，不涉及 Dijkstra 算法所依赖的”最短距离不可被负边改小”这一条件。

7.3 唯一性

• 若所有边权互不相同，则最小生成树唯一；

• 若存在相同权重的边，最小生成树可能不唯一；

• 即使选择顺序不同，只要每一步都选择合法的最轻跨割边，最终总权重仍然最小。

7.4 算法成立的结构性质

Prim 算法能够使用贪心策略，是因为最小生成树问题具有：

• 割性质：跨越合法割的最轻边是安全边；

• 最优子结构：最小生成树切开后，各部分仍对应相应子图的最优连接结构；

• 贪心选择性质：当前最轻的安全边可以直接确定，无需回溯。

8. 典型例子

8.1 输入图

顶点集合：

$$V=\{1,2,3,4,5,6\}$$

边及权重：

从顶点 1 开始执行 Prim 算法。

8.2 逐步执行

第 0 步：初始化

$$S=\{1\},\qquad T=\varnothing$$

跨越割 $(\{1\},V-\{1\})$ 的边为：

$$(1,2,10),\ (1,4,30),\ (1,5,45)$$

选择最轻边：

$$(1,2,10)$$

第 1 步

$$S=\{1,2\}$$

候选跨割边：

$$(1,4,30),\ (1,5,45),\ (2,6,25),\ (2,5,40),\ (2,3,50)$$

选择：

$$(2,6,25)$$

第 2 步

$$S=\{1,2,6\}$$

此时出现新的较小候选边：

$$(6,3,15),\ (6,4,20),\ (6,5,55)$$

选择：

$$(6,3,15)$$

为什么权重 15 在权重 25 之后才被选中？

Prim 并不是将所有边全局排序。只有当顶点 6 加入 $S$ 后，边 (6,3) 才成为跨越当前割的候选边。

第 3 步

$$S=\{1,2,3,6\}$$

选择最轻跨割边：

$$(6,4,20)$$

第 4 步

$$S=\{1,2,3,4,6\}$$

连接剩余顶点 5 的候选边为：

$$(1,5,45),\ (2,5,40),\ (3,5,35),\ (6,5,55)$$

选择：

$$(3,5,35)$$

8.3 执行表

8.4 最终结果

最小生成树边集为：

$$T=\{ (1,2), (2,6), (6,3), (6,4), (3,5) \}$$

总权重为：

$$\begin{aligned} w(T) &=10+25+15+20+35\\ &=\boxed{105} \end{aligned}$$

验证：

• 覆盖全部 6 个顶点；

• 包含 $6-1=5$ 条边；

• 连通且无环；

• 总权重为 105。

9. 常见错误

错误 1：每次选择全图中最小的边

Prim 只选择跨越当前割 $(S,V-S)$ 的最小边。全局按边权排序是 Kruskal’s Algorithm 的做法。

错误 2：允许选择两个端点都在

$S$ 中的边

这种边不能引入新顶点，加入后还可能形成环，因此不能作为 Prim 的下一条扩展边。

错误 3：认为选择顺序中的边权必须单调递增

Prim 的边权选择顺序不一定递增。新的顶点加入后，可能暴露出权重更小的新候选边。

错误 4：把

key[v] 理解成起点到 v 的路径长度

key[v] 表示的是”当前生成树连接到 v 的最小单边权重”，不是从起点到 v 的累计路径长度。

错误 5：忘记检查图是否连通

如果算法结束后仍有顶点的 parent 为 NIL，说明图可能不连通，无法得到覆盖全部顶点的生成树。

10. 与 Kruskal 算法的对比

11. 复习清单

• 能说出 Prim 的贪心选择是什么
• 能区分树内集合 $S$ 和树外集合 $V-S$
• 能解释 key[v] 与 parent[v] 的含义
• 能手算每轮的候选跨割边
• 能用割性质说明正确性
• 能写出邻接矩阵版本的 $O(V^2)$ 复杂度
• 能写出最小堆版本的 $O(E\log V)$ 复杂度
• 能区分 Prim、Kruskal 和 Dijkstra

12. 参考资料

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd Edition, Chapter 23: Minimum Spanning Trees.

2. Erik D. Demaine, Charles E. Leiserson. Greedy Algorithms and Minimum Spanning Trees, MIT 6.046J/18.401J, Lecture 13, 2005.

3. Kruskal’s Algorithm

4. Greedy Algorithms

5. Graph Theory