常用的十大算法-普利姆算法

普利姆算法

介绍

普利姆算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有（n-1）条边包含所有n个顶点的连通子图，也就是极小连通子图

普利姆算法步骤

1、设G=(V,E)是连通图，T=(U,D)是最小生成树，U,V是顶点集合，E,D是边的集合。
2、若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，顶点标记v的visit[u]=1
3、若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边(ui,vj)加入集合D中，标记visit[vj]=1
4、重复步骤2,直到U与V相等，即所有顶点都被标记访问过，此时D中有n-1条边

普利姆算法实践（修路问题）

有7个村庄（A,B,C,D,E,F,G）,现在需要把7个村庄连通，各个村庄的距离用边线表示权，如何修路保证各个村庄都能连通，并且总的修建公路里程最短。

package algorithm;/*** @author taoke* @desc 普利姆算法（修路问题）* @email 1504806660@qq.com* @date 2022/1/25*/
public class Prim {//最大值private static final int N = 65535;//顶点private static final char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};//临界矩阵，N表示不通private static final int[][] matrix = {{0, 5, 7, N, N, N, 2},{5, 0, N, 9, N, N, 3},{7, N, 0, N, 8, N, N},{N, 9, N, 0, N, 4, N},{N, N, 8, N, 0, 5, 4},{N, N, N, 4, 5, 0, 6},{2, 3, N, N, 4, 6, 0}};/*** 普利姆算法** @param v 从第几个顶点开始*/public static void prim(int v) {//所有顶点是否被访问过boolean[] visited = new boolean[vertex.length];//把当前这个顶点标记为已访问visited[v] = true;//h1,h2表示两个顶点int h1 = -1;int h2 = -1;//初始值int minWeight = N;//顶点数量为vertex个，普利姆算法生成vertex-1条边for (int k = 1; k < vertex.length; k++) {//确定每次生成的子图和哪个顶点的距离最近for (int i = 0; i < vertex.length; i++) {for (int j = 0; j < vertex.length; j++) {if (visited[i] && !visited[j] && matrix[i][j] < minWeight) {//替换minWeight(寻找已访问过的节点和未访问过的节点，权值最小的边)minWeight = matrix[i][j];h1 = i;h2 = j;}}}//找到一条最小的边System.out.println("边<" + vertex[h1] + "," + vertex[h2] + ">权值：" + minWeight);//标记顶点为已访问visited[h2] = true;//重新设置为最大值minWeight = N;}}public static void main(String[] args) {prim(0);}
}

计算结果