Prim 算法

定义

Prim 算法是求最小生成树的贪心算法,由 Vojtěch Jarník 于 1930 年最早提出,后由 Robert Prim 与 Edsger Dijkstra 分别重新发现,故也称 Jarník 算法。

原理

从任意一个顶点开始,维护一棵不断生长的树:每一步在所有连接树内顶点与树外顶点的边中,选权值最小的一条,将对应的树外顶点并入树中,重复直到覆盖全部顶点。用二叉堆实现优先队列时复杂度为 O(E log V),用斐波那契堆可达 O(E + V log V)。

应用

适用于顶点间连接密集的场景,如电路布线、网络拓扑设计等;其逐点扩张的过程与 Dijkstra 算法结构相似,仅比较的键值不同。

优缺点

在稠密图上效率优于 Kruskal,且无需对全部边排序;实现上比 Kruskal 略复杂,需维护每个树外顶点的最小连接边。