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操作（例如数据提取）时，要先发送网络请求，然后等待响应，…