思路
最小生成树以尽可能小的总边长连接带权图的每个节点。Kruskal 算法不是从起点生长出一棵树。它一次查看整张图,一开始每个节点各自是一个部分,然后不断用可用的最短边连接各部分,直到只剩一个部分。
分步说明
把边按从短到长排序,并按此顺序尝试。如果一条边的两个端点位于不同部分,就把它加入树中:两个部分合而为一。如果两个端点已在同一部分中,这条边会形成环,因此跳过。有 n 个节点时,树在加入 n − 1 条边后就完成了,剩下的边根本不需要查看。
一个例子
取以下边:A–B 长度为 1,B–C 为 2,A–C 为 3,C–D 为 4,B–D 为 5。Kruskal 加入 A–B,再加入 B–C,把 C 连到 A–B 这一部分。接下来是 A–C,但 A 和 C 已在同一部分中,它会形成环 A–B–C,因此跳过。C–D 加入 D,现在四个节点构成一棵有三条边的树,总长度为 7。最长的边 B–D 根本没被尝试。
并查集
Kruskal 算法唯一的难题是:这两个节点是否已在同一部分中?并查集结构能回答它。每个部分是一棵由指向代表节点的链接组成的小树。find 沿着链接找到代表;union 把一个代表挂到另一个下面。路径压缩让每个经过的节点直接指向代表,再加上按大小合并,链接保持得很短,每次查询几乎只需常数时间。
历史和速度
Joseph Kruskal 于 1956 年在 Proceedings of the American Mathematical Society 上的一篇短文中发表了这个算法。对边排序是最慢的部分,所以对 E 条边,工作量按 E log E 增长。如果边已经排好序,或者边长是很小的整数,它几乎是线性的。
动手探索
打开应用,按“单步”。尚待尝试的边列在图下方,最短的在前。连接两个部分的边会变成绿色;会形成环的边画成红色虚线。观察几个小部分在图的不同位置生长并合并,并留意最后几条边往往根本没被尝试。
常见问题
Kruskal 算法为什么要对边排序?
这样它加入的每条边都是仍能连接两个部分的最短边。由于切分性质,这种贪心选择总是安全的;而每条被跳过的边都是它会形成的那个环上最长的边,所以从来不需要。
什么是不相交集合结构?
并查集的另一个名字:一种保存若干互不相交集合的结构(这里是不断生长的森林中的各个部分),能快速判断某个元素属于哪个集合,并合并两个集合。
Kruskal 算法适用于不连通的图吗?
适用。它最终会为图的每个连通部分各得到一棵树,即最小生成森林,因为没有边能连接互不连通的部分。
Kruskal 算法还有其他用途吗?
在最后几个部分合并之前提前停止,就能把节点分成若干簇,这就是单链接聚类。在边长随机的网格上运行它,可以生成迷宫。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试 Kruskal 算法