普利姆算法(Prim)解决修路问题

普利姆算法(Prim)解决修路问题

普利姆算法应用当前问题得到的最小生成树思路图解:

java代码

package com.bingym.prim; import java.util.Arrays; public class PrimAlgorithm { /* * 普利姆算法: * 典型的修路问题: * 1)有胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在需要修路把7个村庄连通 * 2)各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里 * 3)问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短? * 思路: 将10条边，连接即可，但是总的里程数不是最小. * 正确的思路，就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少. * 修路问题本质就是就是最小生成树问题: * 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称MST。 * 1)给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树 * 2)N个顶点，一定有N-1条边 * 3)包含全部顶点 * 4)N-1条边都在图中 * 普里姆算法生成最小生成树的思路: * 普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图 * 普利姆的算法如下: * 设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合 * 若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited[u]=1 * 若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边（ui,vj）加入集合D中，标记visited[vj]=1 * 重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边 * */ public static void main(String[] args) { //测试看看图是否创建ok char[] data = new char[]{'A','B','C','D','E','F','G'}; int verxNums = data.length; //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通 int [][]weight=new int[][]{ {10000,5,7,10000,10000,10000,2}, {5,10000,10000,9,10000,10000,3}, {7,10000,10000,10000,8,10000,10000}, {10000,9,10000,10000,10000,4,10000}, {10000,10000,8,10000,10000,5,4}, {10000,10000,10000,4,5,10000,6}, {2,3,10000,10000,4,6,10000},}; //创建MGraph对象 Graph graph = new Graph(verxNums); //创建最小生成树对象 MinTree minTree = new MinTree(); //创建Graph minTree.createGraph(graph,verxNums,data,weight); //输出图 System.out.println("修路图的邻接矩阵为:"); minTree.showGraph(graph); //测试普利姆算法 System.out.println("使得路的总里程数最少的路线为:"); minTree.prim(graph,0);//0:表示谁为开始的顶点(此处表示从A开始进行最小生成树的创建) } } //创建最小生成树 class MinTree { //创建图的邻接矩阵 public void createGraph(Graph graph,int vertexNums,char[] data,int[][] weight) { int i,j; for (i = 0; i < vertexNums; i++) { graph.data[i] = data[i]; for (j = 0; j < vertexNums; j++) { graph.weight[i][j] = weight[i][j]; } } } //显示图的邻接矩阵 public void showGraph(Graph graph) { for (int[] link : graph.weight) { System.out.println(Arrays.toString(link)); } } //编写prim算法,获取最小生成树 public void prim(Graph graph,int start) { //V表示进行最小生成树的开始的顶点 //定义数组visited[]:标记结点(顶点)是否被访问过:默认初始全为0(表示都未访问过) int[] visited = new int[graph.vertexNums]; //标记当前开始的结点的为已经访问 visited[start] = 1; //定义两个下标:表示两个顶点的下标 int vertex1 = -1; int vertex2 = -1; int minWeight = 10000;//先将minWeight初始化一个很大的数,对于路的权值近似为无穷大 for (int k = 1; k < graph.vertexNums; k++) { //因为有 graph.verxs顶点，普利姆算法结束后，有 graph.verxs-1边 for (int i = 0; i < graph.vertexNums; i++) {//i表示已经访问过的结点 for (int j = 0; j < graph.vertexNums; j++) {//j表示还未访问的结点 if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) { //替换minWeight(寻找已经访问过的结点和未访问过的结点间的权值最小的边) minWeight = graph.weight[i][j]; //同时记录此时边的两个顶点 vertex1 = i; vertex2 = j; } } } //此时for循环以后找到了一条最小的了 System.out.println("边<" + graph.data[vertex1] + "," + graph.data[vertex2] + "> 权值:" + minWeight); //将此前未访问的j置为已访问的 visited[vertex2] = 1; //重新将minWeight置为最大值 minWeight = 10000; } } } //定义一个图 class Graph { //图的结点的个数(即顶点)的个数 int vertexNums; int[][] weight;//存放边,即邻接矩阵 char[] data;//存放结点的数据 public Graph(int vertexNums) { this.vertexNums = vertexNums; //初始化结点数组 data = new char[vertexNums]; //初始化邻接矩阵 weight = new int[vertexNums][vertexNums]; } }