kurskal算法更适合稀疏图

kruskal算法伪代码：

int kruskal(){
令最小生成树的边权之和为ans, 最小生成树的当前边数为Num_Edge;
将所有边按边权从小到大排序;
for (从小到大枚举所有的边){
if (当前测试边的两个端点在不同的连通块中){
将测试边加入最小生成树中;
ans += 测试边的边权;
最小生成树的当前边数Num_Edge加一;
当前边数Num_Edge等于顶点数减1是结束循环;
}

 }  
 return ans;  

}

具体实现：

struct edge{
int u, v; //边的两个端点编号
int cost; //边权
}E[MAXV];

bool cmp(edge a, edge b){
return a.cost < b.cost;
}
int father[MAXV]; //并查集数组

//并查集查询函数
int findFather(int x){
int a = x;
while (x != father[x]){
x = father[x];
}

 //路径压缩  
 while (a != father\[a\]){  
     int z = a;  
     a = father\[a\];  
     father\[z\] = x;  
 }

 return x;  

}

//kruskal函数返回最小生成树的边权之和，参数n为顶点个数， m为图的边数
int kruskal(int n, int m){
int ans = , Num_Edge = ; //最小边权之和，当前生成树的边数
//初始化并查集
for (int i = ; i <= n; i++){
father[i] = i;
}

 //对所有边排序  
 sort(E, E + m, cmp);  
 //遍历所有的边  
 for (int i = ; i < m; i++){  
     int faU = findFather(E\[i\].u);        //查询测试边两个端点所在集合的根节点  
     int faV = findFather(E\[i\].v);  
     if (faU != faV){  
         father\[faV\] = faU;  
         ans += E\[i\].cost;  
         Num\_Edge++;  
         if (Num\_Edge == n - ) break;    //如果已经建成了一棵树，跳出循环  
     }  
 }  
 if (Num\_Edge != n - ) return -;        //当图不连通时，返回-1  
 else return ans;        //否则返回最小生成树的边权之和  

}