hongchh 发表于 2016-8-16 17:16:02

Kruskal算法的实现与应用

本帖最后由 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算法最小生成树算法。详细的算法介绍和实现请看下面的博客介绍{:5_91:}
博客地址：http://blog.csdn.net/hongchh/article/details/52204188
**** Hidden Message *****

平面最高_wyc 发表于 2017-7-26 22:23:07

{:10_256:}{:10_256:}{:10_256:}{:10_256:}

青青奇犽 发表于 2023-7-12 14:50:17

谢分享
页: [1]
查看完整版本: Kruskal算法的实现与应用