克鲁斯克尔演算法

克魯斯克爾演算法（英語：Kruskal's algorithm）是一種用來尋找最小生成樹的演算法^[1]，由美國數學家約瑟夫·克魯斯克爾在1956年發表^[2]。用來解決同樣問題的還有普林演算法和布盧瓦卡演算法（英语：Borůvka's algorithm）等。三種演算法都是贪心算法的應用。和布盧瓦卡演算法不同的地方是，克魯斯克爾演算法在圖中存在相同權值的邊時也有效。

克鲁斯克尔演算法
概况
類別	最小生成树
資料結構	并查集
复杂度
平均時間複雜度	${\displaystyle O(|E|\log |V|)}$ 或 ${\displaystyle O(|E|\alpha (|V|))}$
空間複雜度	${\displaystyle O(|E|+|V|)}$
相关变量的定义
${\displaystyle V}$	点集
${\displaystyle E}$	边集

步骤

1. 新建图${\displaystyle G}$ ，${\displaystyle G}$ 中拥有原图中相同的节点，但没有边
2. 将原图中所有的边按权值从小到大排序
3. 从权值最小的边开始，如果这条边连接的两个节点于图${\displaystyle G}$ 中不在同一个连通分量中，则添加这条边到图${\displaystyle G}$ 中
4. 重複3，直至图${\displaystyle G}$ 中所有的节点都在同一个连通分量中

证明

1. 这样的步骤保证了选取的每条边都是桥，因此图${\displaystyle G}$ 构成一个树。
2. 为什麽这一定是最小生成树呢？关键还是步骤3中对边的选取。演算法中总共选取了${\displaystyle n-1}$ 条边，每条边在选取的当时，都是连接两个不同的连通分量的权值最小的边
3. 要证明这条边一定属于最小生成树，可以用反证法：如果这条边不在最小生成树中，它连接的两个连通分量最终还是要连起来的，通过其他的连法，那麽另一种连法与这条边一定构成了环，而环中一定有一条权值大于这条边的边，用这条边将其替换掉，图仍旧保持连通，但总权值减小了。也就是说，如果不选取这条边，最后构成的生成树的总权值一定不会是最小的。

時間複雜度

通过使用路径压缩的并查集，平均时间复杂度为${\displaystyle O(|E|\log |V|)}$ ，其中${\displaystyle E}$ 和${\displaystyle V}$ 分别是图的边集和点集。

此外，如果同时使用路径压缩和按秩合并，时间复杂度可以优化到 ${\displaystyle O(|E|\alpha (|V|))}$ ，其中${\displaystyle \alpha }$ 表示反阿克曼函數。

示例

图例	说明
	AD和CE是最短的两条边，长度为5，其中AD被任意选出，以高亮表示。
	现在CE是不属于环的最短边，长度为5，因此第二个以高亮表示。
	下一条边是长度为6的DF，同样地以高亮表示。
	接下来的最短边是AB和BE，长度均为7。AB被任意选中，并以高亮表示。边BD用红色高亮表示，因为B和D之间已经存在一条（标为绿色的）路径，如果选择它将会构成一个环（ABD）。
	以高亮表示下一条最短边BE，长度为7。这时更多的边用红色高亮标出：会构成环BCE的BC、会构成环DBEA的DE以及会构成环FEBAD的FE。
	最终，标记长度为9的边EG，得到最小生成树，结束算法过程。

伪代码

KRUSKAL-FUNCTION(G, w) 1 F := 空集合 2 for each 图 G 中的顶点 v 3 do 將 v 加入森林 F 4 所有的边(u, v) ∈ E依权重 w 递增排序 5 for each 边(u, v) ∈ E 6 do if u 和 v 不在同一棵子树 7 then F := F ∪ {(u, v)} 8 將 u 和 v 所在的子树合并 

参考源程序

C++ 实现

以下代码基于路径压缩和按秩合并的并查集，时间复杂度 ${\displaystyle O(|E|\alpha (|V|))}$ 。

#include <bits/stdc++.h>  struct DSU {  std::vector<int> fa, sz;  DSU(int n = 0) : fa(n), sz(n, 1) {  std::iota(fa.begin(), fa.end(), 0);  }  int Find(int x) { // 路径压缩  while (x != fa[x])  x = fa[x] = fa[fa[x]];  return x;  }  bool Merge(int x, int y) { // 按秩合并  x = Find(x), y = Find(y);  if (x == y) return false; // 处于同一连通分量  if (sz[x] > sz[y]) std::swap(x, y);  fa[x] = y;  sz[y] += sz[x];  return true;  } }; // 并查集  int main() {  int n, m; // 点数，边数  std::cin >> n >> m;  std::vector<std::tuple<int, int, int>> edge(m);  // 边集，三元组分别表示边权和边的两个端点  for (auto &[w, u, v] : edge)  std::cin >> u >> v >> w;  std::sort(edge.begin(), edge.end()); // 按边权升序排序  DSU dsu(n); // 初始化并查集  long long result = 0; // 最小生成树边权和  for (auto &[w, u, v] : edge)  if (dsu.Merge(u, v)) result += w;  // 合并两个连通分量并统计答案  std::cout << result << std::endl;  return 0; } 

参考文献

1. Cormen, Thomas; Charles E Leiserson, Ronald L Rivest, Clifford Stein. Introduction To Algorithms Third. MIT Press. 2009: 631. ISBN 978-0262258104. 
2. Kruskal, J. B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society. 1956, 7 (1): 48–50. JSTOR 2033241. doi:10.1090/S0002-9939-1956-0078686-7.