Kruskal算法（克鲁斯卡尔算法）---求加权连通图的最小生成树的算法

1.参考资料：

克鲁斯卡尔算法  kruskal算法

 

2.代码实现：

 

#include <iostream>
#include <algorithm>
using namespace std;

int n,m,s;   ///n为无向图的顶点个数，m为边的条数，s用来存放最小生成树的总权值
int root[111];   ///存储父节点

struct Edge{

int a,b;   ///边的两个顶点的编号
int d;   ///边的权值

}edge[11111];

bool cmp(Edge a,Edge b){

return a.d<b.d;

}

int find(int a){   ///寻找父节点

if(root[a]==a)
return a;

return root[a]=find(root[a]);
}

bool Union(int a,int b,int d){   ///合并

if(a==b)   ///a==b说明边的两个顶点属于同一棵树
return 0;   ///所以不需要合并，直接返回

root[a]=b;   ///将a的父节点更新为b，从而将树a,b合并成一棵树

s+=d;   ///将边的权值加到s中

return 1;

}

void Kruskal(){

int i;

for(i=0;i<n;i++)   ///初始化，将各顶点的父节点标记为本身
root[i]=i;

sort(edge,edge+m,cmp);   ///第一步，将所有的边的长度排序，用排序的结果作为
///我们选择边的依据，这里再次体现了贪心算法的思想

s=0;

for(i=0;i<m;i++)   ///遍历所有的边
{
if(Union(find(edge[i].a),find(edge[i].b),edge[i].d))
n--;   ///当合并成功，森林的树就少一颗
}   ///当遍历完所有的边时，如果n!=1，说明该无向图不是连通图，不存在最小生成树

}

int main()
{


return 0;
}