算法-21-普利姆算法
二十一、普利姆算法（Prim）
0、最小生成树
从一个带有权值的无向连同图中，选择出一颗所有边上权值的和最小的树，这就是最小生成树（Minimum Spanning Tree, MST）。
特点：
- 有n个顶点，则对应n-1条边
- 节点包含全部的顶点
生成最小生成树的算法主要是Prim和Kruskal
1、Prim算法概念
在包含n个顶点的连通图中，找出只有n-1条边包含所有n个顶点的连通图，这就是极小连通图。
2、过程
-
从指定的起始顶点开始查找。
-
创建一个和顶点数组长度一样的数组，用于标记某个顶点是否已访问过。
-
连通图有n个顶点，则含有n-1条边。可以用一个循环来实现边（路径）的查找。
-
查找边，通过两层嵌套循环，来实现起始顶点到另外某个终止顶点的查找。条件是起始顶点已访问过，终止顶点未访问过，且他们之间的权重是当前所有起始到终止的最小权重。
两层循环过后，可以找到一条最小权重的路径。
-
重复步骤4，直到步骤3的循环结束为止。
可以用一个极大值，来表示一个无法直接连通的权重。
3、示例
[A]---5---[B]/ \ / \7 2 3 9/ \ / \
[C] [G] [D]\ / \ /8 4 6 4\ / \ /[E]---5---[F]七个顶点，顶点和顶点间存在通路，且含有权重
class MST<T> {public void prim(Graph<T> graph) {prim(graph, 0); // 从第一个顶点开始查找}private void prim(Graph<T> graph, int begin) {int vertexCount = graph.getVertexCount();if (0 > begin || begin >= vertexCount) {throw new IllegalArgumentException("非法起始顶点索引");}T[] data = graph.getData();int[][] weightArray = graph.getWeightArray();boolean[] searched = new boolean[vertexCount];searched[begin] = true; // 标记为已访问int v1 = -1本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！