基本思想：（1）构造一个只含n个顶点，边集为空的子图。若将图中各个顶点看成一棵树的根节点，则它是一个含有n棵树的森林。（2）从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图。也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之（3）依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
大白话：（1）将图中的所有边都去掉。（2）将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环（3）重复上一步直到连接所有顶点，此时就生成了最小生成树。这是一种贪心策略。
难点：判断某条边<u, v>的加入是否会在已经选定的边集集合中形成环。
解决办法：使用并查集，分别找出两个顶点u, v所在树的根节点。若根节点相同，说明u, v在同一棵树中，则u, v连接起来会形成环；若根节点不同，则u, v不在一棵树中，连接起来不会形成环，而是将两棵树合并。
克鲁斯卡尔算法的时间复杂度为O（eloge）(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。
克鲁斯卡尔算法从另一途径求网的最小生成树。假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{∮}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
void kruskal(edgeset ge, int n, int e) //ge为权值按照从小到大的边集数组 { int set[MAX], v1, v2, i, j; for(i = 1; i <=n; i++) //set中每个元素赋初值 { set[i] = 0; } i = 1; //i表示获取的生成树中的边数，初值为1 j = 1; //j表示ge中的下标，初始值为1 while(j < n && i <= e) //检查该边是否加入到了生成树中 { v1 = seeks(set, ge[i].beginver); v2 = seeks(set, ge[i].endver); if(v1 != v2) { printf("(%d, %d)", ge[i].beginver, ge[i].endver); set[v1] = v2; j++; } i++; } } |
