鱼C论坛

 找回密码
 立即注册
查看: 2758|回复: 2

[技术交流] Kruskal算法的实现与应用

[复制链接]
发表于 2016-8-16 17:16:02 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 hongchh 于 2016-8-16 17:26 编辑

问题背景:
假设我们有n个位置的集合V={v1, v2, …, vn},我们想在它们顶部建立一个通信网络,网络应该是连通的,即任何两个位置vi和vj之间至少存在一条路径可以相互到达。对于确定的两个位置(vi,vj),假设在这两个位置之间建立网络连接的费用为c(i,j),c(i,j) > 0。将上述问题抽象成一个无向图G=(V,E),用图来表示可能被建立的链接的集合,图的每个结点代表每个位置,图的每条边e的长度表示该边连接的两个结点vi和vj之间建立网络连接的费用c(i,j)。为了求得最小的建造费用,只需要找到n-1条边将n个结点连接起来并确保图的连通性,然后这n-1条边的权值尽可能小。抽象为图之后上述问题可以用最小生成树模型来解决。
解决方案:
使用Kruskal算法最小生成树算法。详细的算法介绍和实现请看下面的博客介绍
博客地址:http://blog.csdn.net/hongchh/article/details/52204188
游客,如果您要查看本帖隐藏内容请回复
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-26 22:23:07 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-7-12 14:50:17 | 显示全部楼层
谢分享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 19:02

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表