最小生成树
1926 年,Otakar Borůvka 受托以尽可能低的成本规划南摩拉维亚(Moravia)的电网。他的问题——如何用最短的线路总长度连接每个地方——就是最小生成树问题,而它拥有整个计算机科学中最简单、最优雅的一些解法。
问题
取一张边带有长度(或代价)的连通图。生成树是连接所有节点且不含环的一组边;有 n 个节点时,它总是恰好有 n − 1 条边,因为每条边多连接一个节点。在所有生成树中,最小生成树的总长度最小。一张图可能有极多的生成树,但没有必要逐一尝试。
为什么贪心可行
把节点以任意方式分成两组。跨越两组的最短边总是属于某棵最小生成树:如果一棵树改用了一条更长的跨越边,把它换成那条更短的边,就能以更低的代价连接同样的节点。这就是切分性质。与之相对的是环性质:任何环上最长的边都不是必需的。下面两种算法只是不断应用这些规则。
一个例子
取以下边:A–B 长度为 1,B–C 为 2,A–C 为 3,C–D 为 4,B–D 为 5。Kruskal 算法取 A–B,再取 B–C,然后跳过 A–C,因为 A 和 C 已经连通,它会形成环,接着取 C–D。这棵树有三条边、四个节点,于是完成,总长度为 7,而 B–D 根本没被查看。从 A 出发的 Prim 算法先通过 A–B 加入 B;作为到 C 的路线,B 的边 B–C (2) 胜过 A–C (3),所以 C 通过 B–C 加入;C 的边 C–D (4) 胜过 B–D (5),所以 D 通过 C–D 加入。同一棵树,同样是 7。
Kruskal、Prim 和 Borůvka
Kruskal 算法由 Joseph Kruskal 于 1956 年发表,它对边排序,并用并查集结构跳过同一部分内部的边,因此工作量按 E log E 增长。Prim 算法最早由 Vojtěch Jarník 于 1930 年提出,后来由 Robert Prim 于 1957 年、Edsger Dijkstra 于 1959 年重新发现;使用二叉堆时工作量按 E log V 增长,使用简单数组时按 V² 增长,适合稠密图。Borůvka 1926 年的算法让每个部分同时选取自己最短的外连边,适合并行计算机。
应用
最小生成树用于设计廉价的电缆、管道和道路网络。它们能把数据分成簇:删去树中最长的几条边,剩下的各个部分就是簇。当距离满足三角不等式时,它们能为旅行商问题快速给出一条路线,长度最多是最优路线的两倍。此外,在边长随机的网格上运行 Kruskal 或 Prim 算法,是生成迷宫的经典方法。
动手探索
打开应用,选择 Kruskal 或 Prim,然后按“单步”。使用 Kruskal 时,尚待尝试的边按从短到长列在图的下方;会形成环的边画成红色虚线。使用 Prim 时,等待加入的节点连同其最佳边的长度一起列出,最佳边画成虚线。在同一张图上运行两者并比较:顺序不同,但总长度总是相同。
常见问题
生成树有多少条边?
恰好比节点数少一条。边再少就无法连接所有节点,再多一条就必然形成环。
Kruskal 和 Prim 哪个更快?
对边排序的 Kruskal 算法通常更简单,在边很少的稀疏图上很快。使用堆的 Prim 算法在稠密图上表现良好;使用普通数组时,无论有多少条边,它都需要大约 V² 步。
什么是并查集?
一种记录哪些节点属于同一部分的数据结构。它能几乎瞬间回答“这两个节点连通吗?”并合并两个部分,这正是 Kruskal 算法对每条边都需要做的。
最小生成树适用于有向图吗?
不能直接适用。对于有单向边的图,对应的问题是最小树形图,可用 Chu–Liu/Edmonds 算法求解。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
构建最小生成树