Kruskal算法
2021/10/11 11:14:39
本文主要是介绍Kruskal算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
全知识整理目录
数据结构整理的目录包括了许多的数据结构相关知识。
目录
概述
算法的过程
算法代码
概述
Kruskal算法是什么?
Kruskal算法是求最小生成树的一种算法,也是一种朴素算法,这种算法就是,在所有的结点当中,每次选择未被连接的权值最小的边。
那么最小生成树又是什么呢?
连通的,最小权值的图,就称为最小生成树。
算法的过程
Kruskal算法又称为加边法,就是把最短的边,一条条加起来生成的树。
算法代码
/* * 克鲁斯卡尔(Kruskal)最小生成树 */ void kruskal(Graph G) { int i,m,n,p1,p2; int length; int index = 0; // rets数组的索引 int vends[MAX]={0}; // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。 EData rets[MAX]; // 结果数组,保存kruskal最小生成树的边 EData *edges; // 图对应的所有边 // 获取"图中所有的边" edges = get_edges(G); // 将边按照"权"的大小进行排序(从小到大) sorted_edges(edges, G.edgnum); for (i=0; i<G.edgnum; i++) { p1 = get_position(G, edges[i].start); // 获取第i条边的"起点"的序号 p2 = get_position(G, edges[i].end); // 获取第i条边的"终点"的序号 m = get_end(vends, p1); // 获取p1在"已有的最小生成树"中的终点 n = get_end(vends, p2); // 获取p2在"已有的最小生成树"中的终点 // 如果m!=n,意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路 if (m != n) { vends[m] = n; // 设置m在"已有的最小生成树"中的终点为n rets[index++] = edges[i]; // 保存结果 } } free(edges); // 统计并打印"kruskal最小生成树"的信息 length = 0; for (i = 0; i < index; i++) length += rets[i].weight; printf("Kruskal=%d: ", length); for (i = 0; i < index; i++) printf("(%c,%c) ", rets[i].start, rets[i].end); printf("\n"); }
参考
克鲁斯卡尔(Kruskal)C语言的实现
最小生成树的两种方法(Kruskal算法和Prim算法)
这篇关于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导出功能如何实现