Prim 算法 | Codeboy's Blog

形式陈述

给定连通有限无向带权图 $G=(V,E)$ ，Prim 算法选择任意根 $r$ ，维护已纳入顶点集 $S$ 与树边集 $F$ 。初始化 $S=\varnothing$ ，令 $key[r]=0$ 、其他顶点键为 $+\infty$ 。每次取尚未纳入且键最小的顶点 $v$ ，若 $v\ne r$ 就把记录的边 $(parent[v],v)$ 加入 $F$ ；随后令 $v$ 进入 $S$ ，并用每条 $vw$ （ $w\notin S$ ）更新

key[w]\leftarrow\min\{key[w],w(vw)\}.

若键严格减小，同时记录该边的 ID 和 $parent[w]=v$ 。当 $S$ 非空时， $key[w]$ 正是外部顶点 $w$ 与 $S$ 相连的最轻单边权重；全局最小键因此对应割 $(S,V\setminus S)$ 的一条轻边。

正确性不变量是 $F$ 包含于某棵最小生成树。设下一条边 $e$ 跨当前割，取一棵包含 $F$ 的 MST $T$ 。若 $e\notin T$ ，把 $e$ 加入 $T$ 会形成圈，圈上另有一条边 $f$ 跨同一割。由 $e$ 是割上轻边， $w(e)\le w(f)$ ；以 $e$ 替换 $f$ 仍是 MST 且包含新的 $F$ 。归纳到 $|V|-1$ 条边即得最优生成树，这就是本算法的贪心证书。

键由最小优先队列维护。设 $n=|V|\ge1$ 、 $m=|E|$ ，权重比较为单位成本：

邻接表加带句柄二叉堆执行 $n$ 次 extract-min、至多 $2m$ 次边检查和 $m$ 次有效 decrease-key，最坏时间 $O((n+m)\log(n+1))$ ；连通且 $n\ge2$ 时可简写为 $O(m\log n)$ ，辅助空间 $O(n)$ ；
惰性插入新键而不做 decrease-key 时，从单个根记录开始，总插入数至多 $m+1$ ，时间为 $O(n+(m+1)\log(m+2))$ 、空间为 $O(n+m)$ ；
Fibonacci 堆的摊还操作界给出整个算法确定性最坏总时间 $O(m+n\log(n+1))$ ；
邻接矩阵配合长度为 $n$ 的键数组，每轮线性寻找最小键，总时间 $\Theta(n^2)$ 、辅助空间 $O(n)$ （不计矩阵）。

直觉

Prim 只生长一个连通块。外部顶点的键不表示它离根有多远；它记录“现在把该点接入树的最便宜单边”。每次接入后，只有新顶点的邻边可能改善其他键，因此无需反复扫描整个割。

它与 Dijkstra 都可写成“取最小键、扫描邻边”，但两个键的代数含义不同。Dijkstra 用 $d[u]+w(u,v)$ 累加路径成本；Prim 只比较单边 $w(u,v)$ 。相同的数据结构外观不能替代各自的最短路定型证明与 MST 割交换证明。

例子与边界

设边及权重为

sa:2,\quad sb:5,\quad ab:1,\quad ac:4,\quad bc:3.

从 $s$ 开始，先以边 $sa$ 、键 $2$ 接入 $a$ ；扫描 $a$ 后把 $b$ 的键由 $5$ 降为 $1$ 、把 $c$ 设为 $4$ 。接着取 $b$ 及边 $ab$ ，再把 $c$ 降为 $3$ ；最后取 $c$ 及边 $bc$ 。树边权为 $2+1+3=6$ 。若误把键更新成从 $s$ 累加的距离， $b$ 会取路径成本 $3$ ，算法状态已经变成最短路而非 MST。

相等权边可能给出多棵 MST，起点与平局规则只改变具体输出，不改变最小总权。负权边会优先接入，但不破坏割性质。平行边应分别比较，外部顶点只保留其中当前最轻的一条及其边 ID；自环永远不跨割，应忽略。

单次 Prim 只能覆盖根所在连通分量。若优先队列最小键变为 $+\infty$ ，说明当前分量已结束；从一个未纳入顶点重启并把它的键置零，可得到整张非连通图的最小生成森林。实现若使用惰性堆记录，弹出后必须检查顶点是否已纳入以及键是否仍为当前值。

推论与应用

图表示决定 Prim 能否只扫描真实邻边。稠密显式图中， $\Theta(n^2)$ 矩阵实现常比指针堆简单；稀疏图通常使用邻接表与堆。在欧氏完全图等隐式稠密输入中，边并未全部列出，几何候选结构可以避免物化 $\Theta(n^2)$ 条边，但那是利用额外度量结构的专门算法。

Kruskal 算法从许多单点分量出发，按全局边序逐渐合并；Prim 始终只有一棵活动树。Borůvka 算法又让所有分量并行选择出边。三者共享割性质，但 Prim 的键更新、Kruskal 的排序和 Borůvka 的轮收缩不能互换复杂度结论。

参考资料

Robert C. Prim, “Shortest Connection Networks and Some Generalizations,” Bell System Technical Journal 36(6), 1957, pp. 1389–1401。
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，§21.2。
Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，§4.5。

形式陈述 ​

反向链接

形式陈述