最近学了Prim普里姆算法,感觉老师讲的不是很清晰,所以自己去搜集了一些关于Prim算法的资料,整理到自己的笔记里。
普里姆算法求最小生成树,也就是在包含n个顶点的连通图中,找出只有(n-1)条边包含所有n个顶点的连通子图,也就是所谓的极小连通子图。
最小生成树:简称MST,给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树。
Prim普里姆算法描述:
使用的图:
import java.util.Arrays; /** * @author 梅效轲 * @version 1.0 */ public class PrimAlgo { public static void main(String[] args) { char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int verxs = data.length; //邻接矩阵 0表示不连通 int[][] weight = new int[][]{ {99999, 5, 7, 99999, 99999, 99999, 2}, {5, 99999, 99999, 9, 99999, 99999, 3}, {7, 99999, 99999, 99999, 8, 99999, 99999}, {99999, 9, 99999, 99999, 99999, 4, 99999}, {99999, 99999, 8, 99999, 99999, 5, 4}, {99999, 99999, 99999, 4, 5, 99999, 6}, {2, 3, 99999, 99999, 4, 6, 99999} }; //创建MGraph对象 MGraph graph = new MGraph(verxs); //创建MinTree对象 MinTree minTree = new MinTree(); minTree.creatGraph(graph, verxs, data, weight); //输出一下 minTree.showGraph(graph); //测试prim算法 minTree.prim(graph, 0); } } class MinTree { //创建图的邻接矩阵 /** * @param graph 图对象 * @param verxs 图的顶点个数 * @param data 图的各个对应顶点的值 * @param weight 图的邻接矩阵 */ public void creatGraph(MGraph graph, int verxs, char[] data, int[][] weight) { int i, j; for (i = 0; i < verxs; i++) { graph.data[i] = data[i]; for (j = 0; j < verxs; j++) { graph.weight[i][j] = weight[i][j]; } } } //显示图的方法 public void showGraph(MGraph graph) { for (int[] link : graph.weight) { System.out.println(Arrays.toString(link)); } } //编写prim算法,得到最小生成树 public void prim(MGraph graph, int v) { //标记数组,用来标记访问过的顶点 boolean[] visted = new boolean[graph.verxs]; //初始化为都没有访问过 Arrays.fill(visted, false); visted[v] = true; int h1 = -1; int h2 = -1; int minWeight = 99999; for (int k = 1; k < graph.verxs; k++) { //确定每一次生成的子图,和哪个结点的距离最近 for (int i = 0; i < graph.verxs; i++) { for (int j = 0; j < graph.verxs; j++) { if (visted[i] == true && visted[j] == false && graph.weight[i][j] < minWeight) { //替换minWeight minWeight = graph.weight[i][j]; h1 = i; h2 = j; } } } //找到了一条边最小 System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值为" + minWeight); //将当前找到的结点标记为已经访问 visted[h2] = true; //重新设置为最大值 minWeight = 99999; } } } class MGraph { int verxs;//顶点的个数 char[] data;//存放结点数据 int[][] weight;//邻接矩阵 public MGraph(int verxs) { this.verxs = verxs; data = new char[verxs]; weight = new int[verxs][verxs]; } }
最短路径权值和为25