之前对最小生成树Prim算法进行了一定的总结，并给出了代码实现，详见：http://www.cnblogs.com/dzkang2011/p/prim_1.html
一、介绍
由于忙于各类事务，在算法方面的学习有所停滞，现在将求最小生成树的另外一种算法补上，也就是Kruskal算法。有关最小生成树算法正确性的证明见上面链接。
Kruskal算法是一种实现起来较为简单，比较容易理解的算法，在图较为稀疏时能够获得很好的性能，但当图较为稠密时（|E|>>|V|)性能便不如Prim算法。后面我们会根据实际代码对Kruskal算法的时间复杂度进行分析。
Krusksl算法采用并查集（算法导论上的表示为不相交集合）实现。初始时，我们的所有顶点都构成单独的一棵树，也就是说由|V|棵树组成的森林。算法首先要做的是，将所有的边，按权值大小进行非降序排列。然后，按照权值从小到大来选择边，若该边的两个端点不在一棵树中，则将他们合并，并将该边置于最小生成树中。一直访问完所有的边为止。可以看出Kruskal算法属于一种贪心算法，而且能保证找到全局最优解。算法理解相应简单，我们不给出相应的证明，有兴趣的可以去钻研一下算法导论。
二、伪代码
算法的伪代码如下，其中A保存最小生成树，MAKE-SET(v)表示构造一棵只有顶点v的树，FIND-SET(u)表示找u所在树的根节点，Union(u, v)表示合并u和v的所在树：
MST-KRUSKAL(G, W)
A←∅
for each vertex v∈V[G]
do MAKE-SET(v)
sort the eages of E into nondecreasing order by weight w
for each eage(u, v)∈E, teken in nondecreasing order by weight
do if(FIND-SET(u) ≠ FIND-SET(v))
then A←A∪{ (u, v) }
Union(u, v)
return A
三、实现
下面给出C++的实现，之后再来分析时间复杂度：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 #define maxn 110 //最多点个数 8 int n, m; //点个数，边数 9 int parent[maxn]; //父亲节点，当值为-1时表示根节点 10 int ans; //存放最小生成树权值 11 struct eage //边的结构体，u、v为两端点，w为边权值 12 { 13 int u, v, w; 14 }EG[5010]; 15 16 bool cmp(eage a, eage b) //排序调用 17 { 18 return a.w < b.w; 19 } 20 21 int Find(int x) //寻找根节点，判断是否在同一棵树中的依据 22 { 23 if(parent[x] == -1) return x; 24 return Find(parent[x]); 25 } 26 27 void Kruskal() //Kruskal算法，parent能够还原一棵生成树，或者森林 28 { 29 memset(parent, -1, sizeof(parent)); 30 sort(EG+1, EG+m+1, cmp); //按权值将边从小到大排序 31 ans = 0; 32 for(int i = 1; i <= m; i++) //按权值从小到大选择边 33 { 34 int t1 = Find(EG[i].u), t2 = Find(EG[i].v); 35 if(t1 != t2) //若不在同一棵树种则选择该边，合并两棵树 36 { 37 ans += EG[i].w; 38 parent[t1] = t2; 39 } 40 } 41 } 42 int main() 43 { 44 while(~scanf("%d%d", &n,&m)) 45 { 46 for(int i = 1; i <= m; i++) 47 scanf("%d%d%d", &EG[i].u, &EG[i].v, &EG[i].w); 48 Kruskal(); 49 printf("%d ", ans); 50 } 51 return 0; 52 }
四、时间复杂度
分析以上代码中Kruskal算法的时间复杂度，n用V表示，m用E表示：
29行：将V个点父节点都置为-1，时间为O(V)
30行：stl中的sort函数，头文件为#include <algorithm>，时间复杂度为O(E log E)
32-40行：由于FIND-SET是树搜索操作，平均时间复杂度为O(lg V)，因为这几行时间复杂度平均为O(E log V)
综上：总复杂度表示为：O(V) + O(E log E) + O(E log V)；
当图为稠密图时，时间复杂度可表示为 O(E log E)；
一般图基本为稀疏图|E| < |V|^2，时间复杂度可表示为 O(E log V)。
因而，从时间复杂度来看，当图为稀疏图时，Kruskal算法性能和Prim相当，当为稠密图时，Prim性能更好。
五、小技巧
注意每合并两棵树，树的棵树就减少1，当根节点的个数只有一个即只有一棵树时，说明生成了最小生成树，此时程序便可终止，没有必要去查看后面权值更大的边，因而判断根节点的数目，在图较为稠密时，能够提高一定的性能，代码修改如下，图为完全图：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 #define maxn 110 //最多点个数 8 int n, m; //点个数，边数 9 int parent[maxn]; //父亲节点，当值为-1时表示根节点 10 int ans; //存放最小生成树权值 11 struct eage //边的结构体，u、v为两端点，w为边权值 12 { 13 int u, v, w; 14 }EG[5010]; 15 16 bool cmp(eage a, eage b) //排序调用 17 { 18 return a.w < b.w; 19 } 20 21 int Find(int x) //寻找根节点，判断是否在同一棵树中的依据 22 { 23 if(parent[x] == -1) return x; 24 return Find(parent[x]); 25 } 26 27 void Kruskal() //Kruskal算法，parent能够还原一棵生成树，或者森林 28 { 29 memset(parent, -1, sizeof(parent)); 30 int cnt = n; //初始时根节点数目为n个 31 sort(EG+1, EG+m+1, cmp); //按权值将边从小到大排序 32 ans = 0; 33 for(int i = 1; i <= m; i++) //按权值从小到大选择边 34 { 35 if(cnt == 1) break; //当根节点只有1个时，跳出循环 36 int t1 = Find(EG[i].u), t2 = Find(EG[i].v); 37 if(t1 != t2) //若不在同一棵树种则选择该边， 38 { 39 ans += EG[i].w; 40 parent[t1] = t2; 41 cnt--; //每次合并，减少一个根节点 42 } 43 } 44 } 45 int main() 46 { 47 while(scanf("%d", &n), n) 48 { 49 m = n*(n-1)/2; //完全图 50 for(int i = 1; i <= m; i++) 51 scanf("%d%d%d", &EG[i].u, &EG[i].v, &EG[i].w); 52 Kruskal(); 53 printf("%d ", ans); 54 } 55 return 0; 56 }