树边
总长度
已检查的边

  • 当前
  • 在树中
  • 会形成环

更多关于 Kruskal 算法

Kruskal 算法

Kruskal 算法构建最小生成树,即连接所有节点、代价最小的一组边,方法简单得难以想象:按从短到长的顺序取边,只要不形成环就保留。逐步查看分开的部分如何生长并合并成一棵树,以及哪些边被跳过。 按“播放”观看树的生长,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。每条边上的数字是它的长度。图下方是尚待尝试的边,按从短到长排列;两端已经连通的边会形成环,画成红色虚线。“新图”会生成另一张图;可选择节点数和边数。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。

它是如何运作的

  1. 按“播放”,或用“单步”和“后退”一步一步移动。
  2. 拖动步骤滑块可跳到任意位置。尚待尝试的边列在图下方,最短的在前。
  3. 留意画成红色虚线的边:它们会形成环。“新图”会生成另一张图供你尝试。

Kruskal 算法的工作原理

把所有边按从短到长排序。一开始,每个节点各自是一个部分。按顺序尝试各条边:如果一条边连接两个不同的部分,就把它加入树中,两个部分合而为一;如果它的两个端点已在同一部分中,它会形成环,因此跳过。当一切都成为一个部分时停止,这发生在加入的边数比节点数少一时,往往远早于尝试最后一条边。

并查集

对每条边,Kruskal 算法都要问它的两个端点是否已经连通。并查集结构能快速回答:每个部分有一个代表节点,find 沿着链接找到它,union 把一个代表链接到另一个代表下。借助路径压缩和按大小合并这两个简单技巧,每次查询几乎只需常数时间,所以对边排序是最慢的部分,工作量按 E log E 增长。

常见问题

什么是 Kruskal 算法?

一种贪心算法,把所有边按从短到长排序,逐条加入不会与已选边形成环的边,从而构建最小生成树。

Kruskal 算法如何检测环?

当且仅当一条边的两个端点已经通过已选的边连通时,它才会形成环。并查集结构记录哪些节点相互连通,几乎能瞬间回答这个问题。

Kruskal 算法为什么正确?

因为环性质:任何环上最长的边都不是最小生成树所必需的。Kruskal 跳过的每条边,都是它会形成的那个环上最长的边,因为在它之前的边都更短或一样长。

什么时候该用 Kruskal 而不是 Prim?

Kruskal 算法简单,在稀疏图上很快,并且可以直接处理普通的边列表。Prim 算法适合稠密图和以邻接表存储的图。两者找到的树总长度相同。

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

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

准备好尝试了吗?

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

前往编辑器