对于一个给定的连通的无向图 G = (V, E)，希望找到一个无回路的子集 T，T 是 E 的子集，它连接了所有的顶点，且其权值之和为最小。

因为 T 无回路且连接所有的顶点，所以它必然是一棵树，称为生成树（Spanning Tree），因为它生成了图 G。显然，由于树 T 连接了所有的顶点，所以树 T 有 V – 1 条边。一张图 G 可以有很多棵生成树，而把确定权值最小的树 T 的问题称为最小生成树问题（Minimum Spanning Tree）。术语 “最小生成树” 实际上是 “最小权值生成树” 的缩写。

Kruskal 算法提供一种在 O(ElogV) 运行时间确定最小生成树的方案。Kruskal 算法基于贪心算法（Greedy Algorithm）的思想进行设计，其选择的贪心策略就是，每次都选择权重最小的但未形成环路的边加入到生成树中。其算法结构如下：

1. 将所有的边按照权重非递减排序；
2. 选择最小权重的边，判断是否其在当前的生成树中形成了一个环路。如果环路没有形成，则将该边加入树中，否则放弃。
3. 重复步骤 2，直到有 V – 1 条边在生成树中。

上述步骤 2 中使用了 Union-Find 算法来判断是否存在环路。

例如，下面是一个无向连通图 G。

图 G 中包含 9 个顶点和 14 条边，所以期待的最小生成树应包含 (9 – 1) = 8 条边。

首先对所有的边按照权重的非递减顺序排序：

然后从排序后的列表中选择权重最小的边。

1. 选择边 {7, 6}，无环路形成，包含在生成树中。

2. 选择边 {8, 2}，无环路形成，包含在生成树中。

3. 选择边 {6, 5}，无环路形成，包含在生成树中。

4. 选择边 {0, 1}，无环路形成，包含在生成树中。

5. 选择边 {2, 5}，无环路形成，包含在生成树中。

6. 选择边 {8, 6}，有环路形成，放弃。

7. 选择边 {2, 3}，无环路形成，包含在生成树中。

8. 选择边 {7, 8}，有环路形成，放弃。

9. 选择边 {0, 7}，无环路形成，包含在生成树中。

10. 选择边 {1, 2}，有环路形成，放弃。

11. 选择边 {3, 4}，无环路形成，包含在生成树中。

12. 由于当前生成树中已经包含 V – 1 条边，算法结束。

C# 实现的 Kruskal 算法如下。