树边
总长度
已检查的边

  • 当前
  • 在树中
  • 与树相邻
  • 目前最佳边

更多关于 Prim 算法

Prim 算法

Prim 算法构建最小生成树,即连接所有节点、代价最小的一组边,方法是从起点生长出一棵树。每一步,它都加入能通过最短边从树到达的节点。点击一个节点从那里开始,逐步查看等待中的节点、它们的最佳边以及树的生长。 按“播放”观看树的生长,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。点击节点可将其设为起点:树从那里开始生长。每条边上的数字是它的长度。图下方是等待加入的节点,以及各自到树的最佳边的长度,最佳边画成虚线。“新图”会生成另一张图;可选择节点数和边数。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。

它是如何运作的

  1. 点击一个节点设为起点:树从那里开始生长。
  2. 按“播放”,或用“单步”和“后退”一步一步移动。拖动步骤滑块可跳到任意位置。
  3. 观察图下方等待中的节点,以及各自到树的最佳边。“新图”会生成另一张图供你尝试。

Prim 算法的工作原理

从只有一个节点的树开始。树外的每个节点记住它到树的最短边(如果有的话)。反复取出边最短的节点,把它和那条边加入树中,再查看它的边:如果某条边比邻居目前的最佳边更短,它就成为该邻居的最佳边。当所有节点都已加入,树的边数比节点数少一,总长度也尽可能小。

Prim 与 Dijkstra

Prim 算法和 Dijkstra 算法看起来几乎一样:两者都从起点扩展一个区域,并把等待中的节点放在优先队列里。区别在于队列中的数字。Dijkstra 保存每个节点从起点出发的整段距离;Prim 只保存它到树的那条最佳边的长度。所以 Dijkstra 构建的是最短路径树,Prim 构建的是总长度最小的树,这两棵树常常不同。

常见问题

什么是 Prim 算法?

一种贪心算法,从一个起点生长出一棵树来构建带权图的最小生成树,每次加入连接树与树外某个节点的最短边。

起点有影响吗?

只影响顺序:从任何起点出发,Prim 算法最终得到的生成树总长度都同样最小。当某些边长度相等时,树本身可能不同。

Prim 算法是谁发明的?

Vojtěch Jarník 于 1930 年最早描述了它。Robert Prim 于 1957 年、Edsger Dijkstra 于 1959 年分别重新发现了它,所以它也叫 Jarník 算法或 Prim–Jarník 算法。

Prim 算法有多快?

使用二叉堆时,对 V 个节点和 E 条边,工作量按 E log V 增长。若用简单数组代替堆,大约需要 V² 步,这更适合几乎每对节点都相连的稠密图。

我的图会被发送到别处吗?

不会。图的生成和树的构建都在你的浏览器中完成,上次的设置保存在此浏览器的本地存储中。

准备好尝试了吗?

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

前往编辑器