Java如何求最小生成树


这篇文章将为大家详细讲解有关Java如何求最小生成树,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。生成树(SpanningTree):一个连通图的生成树是指一个连通子图,它含有图中全部n个顶点,但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边,如果生成树中再添加一条边,则必定成环。最小生成树(Minimum Spanning Tree):在连通图的所有生成树中,所有边的权值和最小的生成树,称为最小生成树。在生活中,图形结构的应用是最广泛的。比如常见的通信网络搭建路线选择,村庄可以看作顶点,村庄之间如果有通信路径,则算作两点之间的边或者弧,两个村庄之间的通信成本,可以看作边或者弧的权值。上图就是生活中通信网络搭建路线的选择映射到图形结构的案例。顶点作为村庄,村庄之间如果有通信路径则拥有边,村庄的之间的通信搭建成本则是边的权值。一种很常见的需求是要求对于能够通信的村庄都必须通信,并且通信建设成本和最小,毕竟经费“有限”,省下来的经费,嘿嘿!上面的问题,转换为数学模型,就是求一个图的最小生成树的问题,即:选出一条路线,连通了所有能够连通顶点,并且权值和最小。这样的问题已经有了很多种解法,最经典的有两种算法,普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。普里姆(Prim)算法是以某顶点为起点,假设所有顶点均未连接,逐步找各顶点上最小权值的边来连接并构建最小生成树。是以点为目标去构建最小生成树。具体的步骤是: 首先随机选取一个顶点a,寻找顶点a可连接所有的顶点,选择一个权值低的顶点进行连接;然后寻找与这两个顶点或可连接的所有顶点,选择一个权值低的顶点与其中一个顶点进行连接;如此往复n-1次,每次选择距离任意一个已连接末端顶点最短的顶点(而不是距离首个顶点最短的顶点)进行连接,直到所有的顶点都进行连接,至此最小生成树构建完毕。该案例对应着下面实现代码中的案例。在上面的图中,首先选择顶点A作为已连接点,寻找顶点A可连接所有的顶点C、D、F,选择一个权值低的顶点进行连接,这里选择A-C;然后寻找与A或C可连接的所有顶点(排除已连接的点),找到B、D、F,一共有4条边可选,A-D、A-F、C-B、C-D,选择一个权值低的顶点与其中一个顶点进行连接,这里明显选择A-D连接;然后寻找与A或C或D可连接的所有顶点(排除已连接的点),找到B、F,一共有3条边可选,C-B、D-B、A-F,选择一个权值低的顶点与其中一个顶点进行连接,这里明显选择A-F连接;然后寻找与A或C或D或F可连接的所有顶点(排除已连接的点),找到B、G,一共有3条边可选,C-B、D-B、F-G,选择一个权值低的顶点与其中一个顶点进行连接,这里明显选择C-B连接;然后寻找与A或C或D或F或B可连接的所有顶点(排除已连接的点),找到E、G,一共有2条边可选,B-E、F-G,选择一个权值低的顶点与其中一个顶点进行连接,这里明显选择B-E连接;然后寻找与A或C或D或F或B或E可连接的所有顶点(排除已连接的点),找到G,一共有2条边可选,E-G、F-G,选择一个权值低的顶点与其中一个顶点进行连接,这里明显选择E-G连接;所有的顶点连接完毕,此时最小生成树已经构建好了,最小权值为23。克鲁斯卡尔算法(Kruskal)根据边的权值以递增的方式逐渐建立最小生成树,是以边为目标去构建最小生成树。具体的步骤是: 将加权图每个顶点都看做森林,然后将图中每条邻接边的权值按照升序的方式进行排列,接着从排列好的邻接边表中抽取权值最小的边,写入该边的起始顶点和结束顶点,连接顶点将森林构成树,然后读取起始结束顶点的邻接边,优先抽取权值小的邻接边,继续连接顶点将森林构成树。添加邻接边的要求是加入到图中的邻接边不构成回路(环)。如此反复进行,直到已经添加n-1条边为止。至此最小生成树构建完毕。该案例对应着下面实现代码中的案例,传统Kruskal算法过程如下:首先获取边集数组并按照权值重小到大进行排序,在代码中的排序本人直接使用免费云主机域名的sort排序,也可以自己实现堆排序,排序后结果如下:Edge{from=A, to=C, weight=1}
Edge{from=D, to=A, weight=2}
Edge{from=A, to=F, weight=3}
Edge{from=B, to=C, weight=4}
Edge{from=C, to=D, weight=5}
Edge{from=E, to=G, weight=6}
Edge{from=E, to=B, weight=7}
Edge{from=D, to=B, weight=8}
Edge{from=F, to=G, weight=9}循环取出第1条边A-C,判断与已经找到的最小生成树不会形成环,权值总和增加1,继续;循环取出第2条边D-A,判断与已经找到的最小生成树不会形成环,权值总和增加2,继续;循环取出第3条边A-F,判断与已经找到的最小生成树不会形成环,权值总和增加3,继续;循环取出第4条边B-C,判断与已经找到的最小生成树不会形成环,权值总和增加4,继续;循环取出第5条边C-D,判断与已经找到的最小生成树会形成环,该条边丢弃,继续;循环取出第6条边E-G,判断与已经找到的最小生成树不会形成环,权值总和增加6,继续;循环取出第7条边E-B,判断与已经找到的最小生成树不会形成环,权值总和增加7,继续;循环取出第8条边D-B,判断与已经找到的最小生成树会形成环,该条边丢弃,继续;循环取出第9条边F-G,判断与已经找到的最小生成树会形成环,该条边丢弃,继续;此时循环结束,那么最小生成树也已经找到了,最小生成树的权值总和为23。上面步骤中,判断是否形成环很关键,通常的做法是,对已经找到的最小生成树的顶点进行排序(从起点到终点),然后每新添加一条边,就使用新添加边的起点和终点取最小二叉树中寻找,排序后的终点,找到的终点一致,则说明最小生成树加上这条边就会形成环,否则说明不会,那么更新排序的终点。这里的实现能够构造一个基于邻接矩阵实现无向加权图的类,并且提供深度优先遍历和广度优先遍历的方法,提供获取边集数组的方法,提供Prim和Kruskal两种求最小生成树的方法。这里的实现能够构造一个基于邻接表实现无向加权图的类;并且提供深度优先遍历和广度优先遍历的方法,提供获取边集数组的方法,提供Prim和Kruskal两种求最小生成树的方法。关于“Java如何求最小生成树”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

相关推荐: React中怎么获取数据

本篇内容介绍了“React中怎么获取数据”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!   在执行I/O操作(例如数据提取)时,要先发送网络请求,然后等待响应,…

免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 09/29 17:12
下一篇 09/29 17:12

相关推荐