首页 > 代码库 > 最小生成树之Kruskal算法
最小生成树之Kruskal算法
上一篇文章中提到了最小生成树的Prim算法,这一节继续探讨一下最小生成树的Kruskal算法。什么是最小生成树算法上文已经交代过了,所以我们直接从Kruskal的步骤开始介绍。
1.Kruskal算法的步骤:
a.假定拓扑图的边的集合是E,初始化最小生成树边集合G={}。
b. 遍历集合E中的所有元素,并且按照权值的大小进行排序。
c. 找出E中权值最小的边e 。
d .如果边e不和最小生成树集合G中的边构成环路,则将边e加到边集合G中;否则测试下一条权值次小的边,直到满足条件为止。
e. 重复步骤b,直到G=E。
2.举例来说明Kruskal算法的运行过程:
下图是一张普通的拓扑图:
则按照上面Kruskal的算法步骤来遍历,则遍历的边按顺序依次为:
AB DG EF ED BC AE
用彩色笔勾出来为:
3.Kruskal的C语言实现
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> using namespace std; #define MAX 1000 int father[MAX], son[MAX]; int v, l; typedef struct Kruskal //存储邻接矩阵的信息 { int a;//边的起始点 int b;//边的终点 int value;//边的权值 }; bool cmp(const Kruskal & a, const Kruskal & b) { return a.value < b.value; } int unionsearch(int x) //查找根结点+路径压缩 { return x == father[x] ? x : unionsearch(father[x]); } bool join(int x, int y) //边的合并 { int root1, root2; root1 = unionsearch(x); root2 = unionsearch(y); if(root1 == root2) //根节点相同,故为环路 return false; else if(son[root1] >= son[root2]) { father[root2] = root1; son[root1] += son[root2]; } else { father[root1] = root2; son[root2] += son[root1]; } return true; } int main() { int ncase, ltotal, sum, flag; Kruskal edge[MAX]; printf("分别输入顶点的个数和边的条数:\n"); scanf("%d%d", &v, &l);//输入顶点的个数和边的条数 ltotal = 0, sum = 0, flag = 0; for(int i = 1; i <= v; ++i) //初始化每个顶点的父节点和子节点 { father[i] = i; son[i] = 1; } printf("输入每条边的邻接点和权值:\n"); for(int i = 1; i <= l ; ++i) { scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].value);//输入每条边的邻接点和权值 } sort(edge + 1, edge + 1 + l, cmp); //按权值由小到大排序,sort函数的头文件是<algorithm> for(int i = 1; i <= l; ++i) { if(join(edge[i].a, edge[i].b)) { ltotal++; //边数加1 sum += edge[i].value; //记录权值之和 printf("%d->%d \n",edge[i].a,edge[i].b); } if(ltotal == v - 1) //最小生成树条件:边数=顶点数-1 { flag = 1; break; } } if(flag) printf("%d\n", sum); else printf("data error.\n"); system("pause"); return 0; }
注:输入的时候要用数字代替拓扑图中的字母,比如1代表A,2代表B……
4.运行结果
本文出自 “写意” 博客,请务必保留此出处http://8827835.blog.51cto.com/8817835/1429376
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。