Kruskal最小生成树算法的概略描述：

1 T=Φ；

2 while(T的边少于n-1条) {

3 从E中选取一条最小成本的边(v,w)；

4 从E中删去(v,w)；

5 if((v,w)在T中不生成环) {

6 将(v,w)加到T中；

7 else{舍弃(v,w)；}

8 }；//if

9 }//for

　　为了有效地执行第5和第6步，G中的结点的组合方式应该是易于确定结点v和w是否已由早先选择的边所连通的那种。在已连通的情况下，则将边(v,w)舍弃；若不连通，则把(v,w) 加人到T。一种可能的组合方法是把T的同一连通分图中所有结点放到一个集合中(T的各个连通分图都是树)。那么，T中的两个结点是连通的，当且仅当它们在同一个集合中。例如，当要考虑边(2,6)时，这些集合就是｛l,2｝，｛3,4,6｝和｛5｝。结点2和6在不同的集合中，因此这些集合被合并成为{1,2,3,4,6}和｛5｝。要考虑的下一条边是(1,4)。由于结点1和4在同一个集合中，因此该边被舍弃，边(3,5)连结不同集合中的结点，并且产生最终的生成树。使用集合表示和Union和Find算法，可以在几乎是线性的时间内有效地实现第5和第6行。因此，计算时间由第3行和第4行的时间所确定，在最坏情况下第3和第4行的计算时间是О(eloge)。

　　举个例子：

Kruskal算法

line void Kruskal (E,COST[],n,T,minCOST) {

//G有n个结点，E是G的边集。COST(u,v)是边(u,v)的成本。

//T是最小成本生成树的边集，minCOST是它的成本

l float minCOST，COST[n][n]；2 int Parent[n]，T[n-1][2]，n3 以边成本为元素构造一个min一堆；4 Parent=l； //每个结点都在不同的集合中5 i=minCOST=0 ；6 while(i

 

 

引理 设T是无向连通图G的一棵生成树。对于任一条边e∈E(G)，但不属于E(T)，有：①若将e加人到T，则生成一个唯一的环；②从E(T) ∪ {e}中去掉这环中的任意一条边后，剩　　　　　　　　余的边构成G的一棵树。