对于一个给定的连通的无向图 G = (V, E)，希望找到一个无回路的子集 T，T 是 E 的子集，它连接了所有的顶点，且其权值之和为最小。
因为 T 无回路且连接所有的顶点，所以它必然是一棵树，称为生成树（Spanning Tree），因为它生成了图 G。显然，由于树 T 连接了所有的顶点，所以树 T 有 V - 1 条边。一张图 G 可以有很多棵生成树，而把确定权值最小的树 T 的问题称为最小生成树问题（Minimum Spanning Tree）。术语 "最小生成树" 实际上是 "最小权值生成树" 的缩写。
将所有的边按照权重非递减排序；
选择最小权重的边，判断是否其在当前的生成树中形成了一个环路。如果环路没有形成，则将该边加入树中，否则放弃。
重复步骤 2，直到有 V - 1 条边在生成树中。
例如，下面是一个无向连通图 G。
图 G 中包含 9 个顶点和 14 条边，所以期待的最小生成树应包含 (9 - 1) = 8 条边。
首先对所有的边按照权重的非递减顺序排序：
<a></a>
然后从排序后的列表中选择权重最小的边。
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 算法如下。
输出结果如下：
<a href="http://www.geeksforgeeks.org/connectivity-in-a-directed-graph/" target="_blank">Connectivity in a directed graph</a>
<a href="http://www.geeksforgeeks.org/strongly-connected-components/" target="_blank">Strongly Connected Components</a>
<a href="http://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/" target="_blank">Tarjan's Algorithm to find Strongly Connected Components</a>
本文转自匠心十年博客园博客，原文链接：http://www.cnblogs.com/gaochundong/p/kruskal_minimum_spanning_tree.html，如需转载请自行联系原作者