最小生成树(MST)

1. Introduction

一个连通无向有权图 G生成树 Spanning Tree (ST)G 的子图,同时也是一个连接 G 中所有节点的。 一个图 G 可以有很多的生成树 (详见 this 或者 this),而每一个都有不同的总权重(生成树中所有边的权重之和)。

G 的最小生成树 Min(imum) Spanning Tree (MST) 是在所有生成树中,有着最小总权重的生成树。

1-1. 最小生成树(MST)问题

最小生成树 (及其优化) 的问题如下定义: 给定一个连通的无向有权图 G = (V, E), 选择 G 中所有边的一个子集,使得图仍然是连通的,但其边的总权重最小。输出要么是 G 的一个最小生成树 (G 可以有很多最小生成树) 或是其最小的权重和。

1-2. 激励的例子

政府想要用 N-1 条路将 N 个村庄连接起来(这是一个N个节点,N-1条边的生成树)。

路的造价取决于地形,距离等等(这是一个完全的无向有权图,其中有 N*(N-1)/2 个有权重的边)。
你想要最小化造价。你要怎样建这些路呢?(这是一个最小生成树)。

备注:对这个问题有一个更高级的变种解法,详见 这里

1-3. 最小二叉树算法

最小生成树算法有很多种解法。

在此可视化中,我们会学习其中的两种:Kruskal算法和Prim算法。两种都是贪心算法。注意除此两种外,还有其他一些此处未列的解法。

2. 可视化

观看上面最小生成树算法的可视化。

最开始,图中所有的节点和边都被标记成 白底黑字.

在算法的最后, |V|-1 条最小生成树的边 (和所有 |V| 个节点) 都被标记成 橙色 而所有不在最小生成树中的边则为 灰色.

3. 输入图

There are two different sources for specifying an input graph:

  1. Edit Graph: You can edit the currently displayed connected undirected weighted graph or draw your own input graph.
  2. Example Graphs: You can select from the list of example connected undirected weighted graphs to get you started.

4. Kruskal 算法

Kruskal 算法: 一个 O(E log V) 的贪心最小生成树算法。它扩展一个最小生成树的森林,直到将他们组合成一个最小生成树。

Kruskal 算法 需要 一个好的排序算法来对图中的边以权重的非减进行排序 (通常存储在 边列表 内) 和 并查集 (UFDS)来判断/预防成环。

4-1. 基本原理

Kruskal算法先将边以权重非减,较小节点,较大节点的次序排序。
讨论:这是唯一可行的排序次序吗?

4-2. 答案

[This is a hidden slide]

4-3. 基本原理 - continued

然后,Kruskal 算法会遍历这些排好序的边,并贪心的选择下一个不产生环的边。
无需多言,让我们在有三条相同权重边默认示例图上来试试 Kruskal。在继续之前请看完此动画。

4-4. 正确性的证明 - 1

要了解 Kruskal 算法的贪心策略有效,我们定义一个循环不变量:每条被 Kruskal 算法加进树 T 的边 e 都是最小生成树 MST 的一部分。

在 Kruskal 算法主循环的开始,根据定义 T = {} 总是最小生成树的一部分。

Kruskal 算法在主循环中有一个特殊的环检查 (使用 UFDS 数据结构),且只在(相较于之前选中的边)不成环的的情况下将边 e 加入 T。

在主循环结束时,Kruskal 算法只会从连通的无向有权图 G 中选中不成环的 V-1 条边。这表明 Kruskal 算法产生了一个生成树。

在默认示例中个,注意在拿走最初的两条边 0-1 和 0-3之后,Kruskal 算法不能拿走 1-3,因为这会导致环 0-1-3-0。接下来Kruskal 算法会拿走边 0-2 但不会拿走 0-2,因为这会导致环 0-2-3-0。

4-5. 正确性的证明 - 2

我们已经在前面看到 Kruskal 算法在停止时会产生一个生成树 T。但其是否是最小生成树呢?
要证明,我们要注意在 Kruskal 算法的主循环开始前,我们已经将所有边以权重的非减次序排好了序,即后面的边总会有一样或更高的权重。

4-6. 正确性的证明 - 3

在每次循环开始时, T 总是最小生成树的一部分。

如果 Kruskal 算法只添加一条最小权重的边 e (保证其与之前的边不会形成一个环),那么我们可以保证 w(T U e) ≤ w(T U 任何其他不成环的未处理的边) (由于 Kruskal 算法将边排序了 w(e) ≤ w(e')).

因此,在循环结束是,生成树 T 一定会有最小的总权重 w(T), 而 T 就是最终的最小生成树。

在默认的示例中,注意在依次拿走两条边 0-1 和 0-3 且因 1-3 会成环而排除 1-3 之后,我们可以安全的拿走吓一跳最小权重边 0-2 (权重 2),因为拿走任意其他的边(如权重3的边 2-3)会要么生成 另一个 权重相同的最小生成树 (非本示例) 或 另一个 不是最小的生成树 (本示例)。

4-7. 实现简述

Kruskal 算法有两个部分:排序和 Kruskal 算法的主循环。

对边的排序很简单。我们只需用一个 边列表 来排序 E 个边,用 O(E log E) = O(E log V) 的排序算法(或者用C++/Python/Java 的 sorting library)来以权重的非减,较小的节点数,较大的节点数的次序排序。这个 O(E log V) 的复杂度是 Kruskal 算法的瓶颈,因为第二部分其实较快,如下所示。

Kruskal 算法的主循环可以用 并查集 来简单的实现。我们用 IsSameSet(u, v) 来测试以节点 uv 为端点的边 e 是否会导致环(相同的连接分支 -- 有另一条从 uv 的路,所以添加边 (u, v) 会导致成环)。如果 IsSameSet(u, v) 为 false,我们贪心的选择下一个最小的合格边 e 并调用 UnionSet(u, v) 来预防可能的与此边相关的环。这个部分在 O(E) 时间内运行,因为我们认为 UFDS 的 IsSameSet(u, v)UnionSet(u, v) 操作在较小图上以 O(1) 时间运行。

5. Prim 算法

Prim 算法: 另一个 O(E log V) 的贪心最小生成树算法。它从一个起始的源节点开始逐渐扩张到整个图,从而生成一个最小生成树。

Prim 算法需要使用优先队列 (一般用 Binary Heap 来实现但我们也可以用平衡二叉树 Balanced Binary Search Tree) 以权重的非减次序来动态排序当前的边, 一个 邻接表 来找到一个节点的邻居节点, 和一个布尔数组 (直接寻址表) 来帮助判断环。

Prim 算法的另一个名字是 Jarnik-Prim 算法。

5-1. 基本原理

Prim 算法从一个特定的源节点 s 开始(通常是节点0),将所有与 s 相连的边根据其权重从小到大排入一个优先队列;如果权重相同,则根据节点的序号。然后它会重复下述的贪心步骤:如果在优先队列中最前面的边 e: (w, v) 中的 v 还没有被访问过,这意味着我们可以贪心地包括 v 来扩展生成树 T 并将 v 的边排进优先队列中;否则我们放弃边 e (因为Prim算法从节点 s 生成树,v 已被访问过意味着有另外一条从 sv 的路,而添加边 e 会导致环)。

毋再多言,让我们来在默认示例图上试试 Prim(1) (有三条相同权重的边)。我们用 Prim 算法从源节点 s = 1 开始。请在继续之前看完此动画示例。

5-2. 正确性的证明 - 第二部分

Prim 算法是一个 Greedy Algorithm 因为在其循环的每一步,它总是选择下一个权重最小的边 e(这是贪心的!)。

要证明 Prim 算法是正确的,让我们看看下面的简单证明:令 T 为图 G 上用 Prim 算法生成的生成树,而 T* G 上的最小生成树 MST。

T == T*,即 Prim 算法生成和 T* 完全一样的最小生成树,我们就成功了。

但是如果 T != T*...

5-3. 若 T != T*, 第一部分

假设在默认实例中,T = {0-1, 0-3, 0-2}T* = {0-1, 1-3, 0-2}。


ek = (u, v) 为 Prim 算法第 k 轮中第一条选中的不在 T* 中的边 (在示例中 k = 2, e2 = (0, 3), 注意 (0, 3) 不在 T* 中) 。

PT* u v 的路, 再令 e*P 中的一条边,使得一个端点在 Prim 算法 N-1 轮生成的数中而另一个不在 (在示例中, P = 0-1-3e* = (1, 3), 注意节点 1k = 1 轮时就在 T 中).

5-4. 如果 T != T*, 第二部分

如果 e* 的权重比 ek 的权重小,那么 Prim 算法在第 k 轮会选择 e*

所以,可以确定的是 w(e*) ≥ w(ek)。(在示例图中, e* = (1, 3) 有权重 1 而 ek = (0, 3) 也有权重 1).

w(e*) = w(ek), 我们可以任意从 e*ek 中选择一个。当 w(e*) ≥ w(ek), e* 总能在保持最小权重和 T* 的情况下被 ek 替换。(在示例图中, 当我们将 e* = (1, 3) 替换成 ek = (0, 3), 我们将 T* 转换成了 T).

5-5. 正确性的证明 - 第一部分

但是如果 T != T*... (continued)

我们可以重复上述的替换步骤直到 T* = T,然后就可以证明Prim算法生成的生成树是(从源节点 s 开始的)最小生成树,因为不论最佳的最小生成树是什么,它都可以转换成Prim算法输出的最小生成树。

5-6. 实现简述

我们可以用两个著名的数据结构来实现 Prim 算法:

  1. 一个优先队列 (二叉堆 C++ STL priority_queue/Python heapq/Java PriorityQueue 或者 平衡二叉树 C++ STL set/Java TreeSet),和
  2. 一个大小为 V 的布尔数组,本质是一个 直接寻址表 (来判断一个节点有没有被访问过,也就是是否与源节点 s 在一个连通分支内)

有了这些,我们可以在 O(E log V) 时间内运行 Prim 算法,因为我们一次处理一条边,而在优先队列中 Insert((w, v))(w, v) = ExtractMax() 时间为 O(log E) = O(log V2) = O(2 log V) = O(log V)。因为总共有 E 条边,Prim 算法时间复杂度为 O(E log V)。

6. 调查

Quiz: Having seen both Kruskal's and Prim's Algorithms, which one is the better MST algorithm?

Kruskal's Algorithm
It Depends
Prim's Algorithm

讨论:为什么?

6-1. 答案

[This is a hidden slide]

7. 额外内容

你已经几乎完成了最小生成树的基础知识和它的两个经典算法:Kruskal 算法和 Prim 算法(有其他的算法,类似 O(E log V) 的 Boruvka 算法,但并未在此可视化中展示)。我们鼓励你在探索模式中探索更多。

但是,更难的最小生成树问题可能会比基础版本的要更具挑战性。

一旦你已经掌握了这个最小生成树问题,我们鼓励你学习更多更难的图问题,其中最小生成树只是一部分,例如 NP 困难的 (Metric No-Repeat) TSP 和 Steiner Tree 问题。

7-1. 最小生成树问题的变种

我们将最小生成树问题的一些变种放在 Competitive Programming book 一书中。

  1. 最大生成树,
  2. 最小生成子图,
  3. 最小生成森林,
  4. 第二好的生成树,
  5. 最短/最长路径问题,等等

广告:购买CP一书来学习这些变种,并且了解在不同的情况下Kruskal算法更好,而在另一些情况下Prim算法更好

7-2. 在线测验

若想要最小生成树问题或Kruskal/Prim算法中更有挑战性的问题,可以在 MST 的训练模块练习(不需登录,但只有中等难度的练习)。

对NUS学生来说,你可以登录并正式完成此模块,而成就会保存在你的账户中。

7-3. 在线测评练习

这个最小生成树算法会比基本形式的要有挑战性的多。因此,我们建议您尝试下面两道 ACM ICPC 有关最小生成树的竞赛题: UVa 01234 - RACINGKattis - arcticnetwork

尝试他们来证实和提升你对这个问题的理解。

你可以使用我们对Kruskal/Prim算法的实现代码:kruskal.cpp | py | java | ml prim.cpp | py | java | ml

7-4. 讨论

[This is a hidden slide]