Prim 算法

想象从发电站铺设电缆:先连接最近的城镇,再连接离任何已连通地点最近的城镇,依此类推。这就是 Prim 算法,它最终总能得到代价最低的网络。

一张图:一棵树从一个节点生长出来,周围是等待中的节点,它们的最佳边画成虚线,下方列出等待中的节点
一张图:一棵树从一个节点生长出来,周围是等待中的节点,它们的最佳边画成虚线,下方列出等待中的节点

思路

最小生成树以尽可能小的总边长连接带权图的每个节点。Prim 算法从起点向外生长出一棵树来构建它。这棵树从不分裂成几块:每一步恰好有一个新节点通过离开树的最短边加入。

分步说明

把起点放入树中。对树外的每个节点,保存它的最佳边:它到树中任一节点的最短边。然后重复:选出最佳边最短的树外节点,把它连同那条边加入树中,再查看它的边。如果树外的某个邻居现在能通过更短的边到达,这条边就成为它新的最佳边。当所有节点都在树中时停止。

一个例子

取以下边:A–B 长度为 1,B–C 为 2,A–C 为 3,C–D 为 4,B–D 为 5,从 A 开始。A 的边给 B 最佳边 1,给 C 最佳边 3。B 最近,所以通过 A–B 加入;它的边把 C 改进为 2,并给 D 5。C 通过 B–C 加入,它的边 C–D 把 D 改进为 4。最后 D 通过 C–D 加入。树 A–B、B–C、C–D 的总长度为 1 + 2 + 4 = 7。

为什么正确

每一步,节点都分成两组:树中的和树外的。切分性质指出,这样两组之间的最短边总是属于某棵最小生成树。Prim 总是加入恰好这条边,所以它目前建好的树总能补全为一棵最小生成树;当所有节点都加入后,它就是一棵最小生成树。

历史和速度

捷克数学家 Vojtěch Jarník 于 1930 年发表了这个算法。Robert Prim 于 1957 年在 Bell Labs 重新发现了它,Edsger Dijkstra 又于 1959 年再次发现。把等待中的节点放在二叉堆中时,对 V 个节点和 E 条边,工作量按 E log V 增长;用普通数组时约为 V²,在几乎每对节点都相连时更好。用斐波那契堆时为 E + V log V。

动手探索

打开应用,点击一个节点从那里开始,然后按“单步”。树中的节点是绿色,等待中的节点是蓝色,每个等待节点的最佳边画成虚线。等待中的节点列在图下方,并标出最佳边的长度,最短的在前:第一个就是下一个加入的。从不同节点开始,看看顺序如何变化,而总长度保持不变。

常见问题

Prim 算法和 Dijkstra 算法有什么区别?

两者都用优先队列从起点扩展一个区域。Prim 按等待节点到树的那条最佳边的长度排序;Dijkstra 按它从起点出发的整段距离排序。Prim 得到最小生成树,Dijkstra 得到最短路径树。

Prim 算法能处理负的边长吗?

能。与 Dijkstra 算法不同,Prim 只把边彼此比较,所以负长度不会造成问题:它仍能找到总长度最小的生成树。

如果图不连通怎么办?

那么 Prim 算法在到达所有能到达的节点后就会停止:它只给出起点所在部分的最小生成树。从尚未到达的节点再次运行,就能得到最小生成森林。

Prim 算法和 Kruskal 算法哪个更好?

没有哪个总是更好。Prim 适合稠密图和以邻居列表存储的图;Kruskal 适合以边列表给出的稀疏图。两者找到的树总长度相同。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

试试 Prim 算法