本文主要是介绍常用的十大算法-普利姆算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
普利姆算法
介绍
普利姆算法求最小生成树,也就是在包含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);}
}
计算结果
这篇关于常用的十大算法-普利姆算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!