1. 克鲁斯卡尔算法简介
克鲁斯卡尔算法是一种用来寻找最小生成树的算法(用来求加权连通图的最小生成树的算法)。在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。
而具体的操作过程为：
a) 将图的所有连接线去掉，只剩顶点
b) 从图的边集数组中找到权值最小的边，将边的两个顶点连接起来
c) 继续寻找权值最小的边，将两个顶点之间连接起来，如果选择的边使得最小生成树出现了环路，则放弃该边，选择权值次小的边
d) 直到所有的顶点都被连接在一起并且没有环路，最小生成树就生成了。
2. 两个核心问题
问题一 对图的所有边按照权值大小进行排序。
问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。
问题一直接采用排序算法进行排序即可。
问题二的核心思想是记录处理，处理方式是：记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。
3. 代码实现
依旧是仅供参考#include
#defineMAXEDGE100
#defineMAXVERTEX100
typedefstructEdge{
intbegin;//边的起点
intend;//边的终点
intwight;//边的权值
}Edge;
typedefstructGraph{
charvertex[MAXVERTEX];//顶点
Edgeedges[MAXEDGE];//边
intnumvertex,numedges;//顶点和边的个数
}MGraph;
voidCreateGraph(MGraph*G){
printf("请输入顶点和边的个数：\n");
scanf("%d%d",&G->numvertex,&G->numedges);
printf("请输入顶点：\n");
getchar();//利用该函数除去上一系我们在输入结束时按得回车符
for(inti=0;inumvertex;i++){
scanf("%c",&G->vertex[i]);
}
printf("按权值从小到大输入边(vi,vj)对应的起点和终点的下标，begin，end以及权值wight:\n");
for(intk=0;knumedges;k++){
Edgee;
scanf("%d%d%d",&e.begin,&e.end,&e.wight);
G->edges[k]=e;
}
}
intFind(int*parent,intf){
while(parent[f]>0){
f=parent[f];
}
returnf;
}
//最小生成树，克鲁斯卡尔算法
voidKruskal(MGraph*G){
intparent[MAXVERTEX];//存放最小生成树的顶点
for(inti=0;inumvertex;i++){
parent[i]=0;
}
intm,n;
for(inti=0;inumedges;i++){
n=Find(parent,G->edges[i].begin);
m=Find(parent,G->edges[i].end);
if(n!=m){//m=n说明有环
parent[n]=m;
printf("(%d,%d)%d\t",G->edges[i].begin,G->edges[i].end,G->edges[i].wight);//打印边和权值
}
}
}
intmain(){
MGraphG;
CreateGraph(&G);
Kruskal(&G);
return0;
}
如果觉得《克鲁斯卡尔算法c语言 最小生成树-克鲁斯卡尔(Kruskal)算法》对你有帮助，请点赞、收藏，并留下你的观点哦！
