最小生成树（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. Visualisation

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

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

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

3. 输入图

有两种不同的方式来指定输入图：

  1. 编辑图：您可以编辑当前显示的连通无向加权图，或者绘制您自己的输入图。
  2. 示例图：您可以从连通无向加权图的示例列表中选择，以便开始。

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) 来测试以节点 u 和 v 为端点的边 e 是否会导致环（相同的连接分支 -- 有另一条从 u 到 v 的路，所以添加边 (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 已被访问过意味着有另外一条从 s 到 v 的路，而添加边 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* 中) 。

令 P 为 T* 中 u 到 v 的路, 再令 e* 为 P 中的一条边，使得一个端点在 Prim 算法 N-1 轮生成的数中而另一个不在 (在示例中, P = 0-1-3 而 e* = (1, 3), 注意节点 1 在 k = 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?

It Depends
Kruskal's Algorithm
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 - RACING 和 Kattis - arcticnetwork。

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

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

7-4. 讨论

[This is a hidden slide]