Kruskal 算法

对边排序,选最短的,永不成环。Kruskal 算法也许是最简单的贪心算法,却总能找到连接图中所有节点的最廉价方式。

一张图:一棵树的几个部分同时生长,一条会形成环而被跳过的边画成红色虚线,下方列出尚待尝试的边
一张图:一棵树的几个部分同时生长,一条会形成环而被跳过的边画成红色虚线,下方列出尚待尝试的边

思路

最小生成树以尽可能小的总边长连接带权图的每个节点。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 算法