kruskal算法生成最小生成树
2021/5/30 1:19:59
本文主要是介绍kruskal算法生成最小生成树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
kurskal算法更适合稀疏图
kruskal算法伪代码:
1 int kruskal(){ 2 令最小生成树的边权之和为ans, 最小生成树的当前边数为Num_Edge; 3 将所有边按边权从小到大排序; 4 for (从小到大枚举所有的边){ 5 if (当前测试边的两个端点在不同的连通块中){ 6 将测试边加入最小生成树中; 7 ans += 测试边的边权; 8 最小生成树的当前边数Num_Edge加一; 9 当前边数Num_Edge等于顶点数减1是结束循环; 10 } 11 12 } 13 return ans; 14 }
具体实现:
1 struct edge{ 2 int u, v; //边的两个端点编号 3 int cost; //边权 4 }E[MAXV]; 5 6 bool cmp(edge a, edge b){ 7 return a.cost < b.cost; 8 } 9 int father[MAXV]; //并查集数组 10 11 //并查集查询函数 12 int findFather(int x){ 13 int a = x; 14 while (x != father[x]){ 15 x = father[x]; 16 } 17 18 //路径压缩 19 while (a != father[a]){ 20 int z = a; 21 a = father[a]; 22 father[z] = x; 23 } 24 25 return x; 26 } 27 28 //kruskal函数返回最小生成树的边权之和,参数n为顶点个数, m为图的边数 29 int kruskal(int n, int m){ 30 int ans = 0, Num_Edge = 0; //最小边权之和,当前生成树的边数 31 //初始化并查集 32 for (int i = 1; i <= n; i++){ 33 father[i] = i; 34 } 35 36 //对所有边排序 37 sort(E, E + m, cmp); 38 //遍历所有的边 39 for (int i = 0; i < m; i++){ 40 int faU = findFather(E[i].u); //查询测试边两个端点所在集合的根节点 41 int faV = findFather(E[i].v); 42 if (faU != faV){ 43 father[faV] = faU; 44 ans += E[i].cost; 45 Num_Edge++; 46 if (Num_Edge == n - 1) break; //如果已经建成了一棵树,跳出循环 47 } 48 } 49 if (Num_Edge != n - 1) return -1; //当图不连通时,返回-1 50 else return ans; //否则返回最小生成树的边权之和 51 }
这篇关于kruskal算法生成最小生成树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现