树边
总长度
已检查的边

  • 当前
  • 在树中
  • 与树相邻
  • 目前最佳边
  • 会形成环

更多关于最小生成树

最小生成树

你想用电缆连接每个城镇、用水管连接每户人家,或连接网络中的每台计算机,并尽量少用材料。答案就是最小生成树:以最小总长度连接所有节点的一组边。选择 Kruskal 或 Prim 算法,逐步查看树如何生长,每次加入一条允许的最短边。 按“播放”观看树的生长,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。选择算法:Kruskal 按从短到长的顺序尝试各条边,Prim 从起点生长出一棵树;点击节点可将其设为 Prim 的起点。每条边上的数字是它的长度。图下方列出尚待尝试的边,或等待加入的节点及其到树的最佳边的长度。“新图”会生成另一张图;可选择节点数和边数。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。

它是如何运作的

  1. 选择 Kruskal 或 Prim 算法。使用 Prim 时,点击一个节点设为起点。
  2. 按“播放”,或用“单步”和“后退”一步一步移动。拖动步骤滑块可跳到任意位置。
  3. 观察边加入树中、总长度不断增长。“新图”会生成另一张图供你尝试。

Kruskal 算法

把所有边按从短到长排序,并按此顺序尝试。如果一条边连接两个尚未连通的部分,就把它加入树中。如果它的两个端点已经通过树连通,它会形成环,因此跳过。当树的边数比节点数少一时停止。为了快速判断两个节点是否已经连通,Kruskal 算法用并查集结构保存各个部分。

Prim 算法

从只有一个节点的树开始。树外的每个节点记住它到树的最短边。反复加入边最短的节点及那条边,然后检查它的边:其中某条可能为邻居提供一条更短的入树路线。Prim 算法看起来像 Dijkstra 算法,但它比较的是单条边,而不是从起点出发的整段距离。两种算法最终得到的总长度总是相同。

常见问题

什么是最小生成树?

对于边有长度的连通图,生成树是连接所有节点且不含环的一组边;有 n 个节点时,它总是有 n − 1 条边。最小生成树是总长度尽可能小的生成树。

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

Kruskal 算法按从短到长的顺序查看整张图的边,把分散的部分合并成一棵树。Prim 算法从起点生长出一棵树,每次加入离开这棵树的最短边。两者都是贪心算法,找到的树总长度相同;Kruskal 适合稀疏图,Prim 适合稠密图。

最小生成树是唯一的吗?

当所有边的长度都不同时,是唯一的。当某些长度相等时,可能有好几棵总长度同为最小的树,算法会因处理平局的方式不同而选出不同的树。

最小生成树和最短路径一样吗?

不一样。最小生成树让所有边的总长度尽量小,但树中两个节点之间的路径可能比它们的最短路径长得多。要求最短路径,请用 Dijkstra 算法。

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

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

准备好尝试了吗?

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

前往编辑器