Prim算法解决最小生成树 (解决修路问题)

一.什么是Prim算法

       普里姆算法查找最小生成树的过程,采用了贪心算法的思想。对于包含 N 个顶点的连通网,普里姆算法每次从连通网中找出一个权值最小的边,这样的操作重复 N-1 次,由 N-1 条权值最小的边组成的生成树就是最小生成树。

 二.Prim实现的思路

  1. 将连通网中的所有顶点分为两类(假设为 A 类(结点已访问)和 B 类(结点未访问)。  初  始状态下,所有顶点位于 B 类;  
  2. 选择任意一个顶点,将其从 B 类移动到 A 类;  (把这个结点标志为访问了)
  3. 从 B 类的所有顶点出发,找出一条连接着 A 类中的某个顶点且权值最小的边,将此边连接着的 A 类中的顶点移动到 B 类(双重循环 ,找出访问节点和未访问结点之间最小的边)
  4. 重复执行第 3  步,直至 B 类中的所有顶点全部移动到 A 类,恰好可以找到 N-1 条边。     (循环实现 构成N-1次)

假如从顶点A出发,顶点 B、C、D 到顶点 A 的权值分别为 2、4、2,所以,对于顶点 A 来说,顶点 B 和顶点 D 到 A 的权值最小,假设先找到的顶点 B:

Prim算法解决最小生成树 (解决修路问题)Prim算法解决最小生成树 (解决修路问题)Prim算法解决最小生成树 (解决修路问题)


继续分析顶点 C 和 D,顶点 C 到 B 的权值为 3,到 A 的权值为 4;顶点 D 到 A 的权值为 2,到 B 的权值为无穷大(如果之间没有直接通路,设定权值为无穷大)。所以顶点 D 到 A 的权值最小:
最后,只剩下顶点 C,到 A 的权值为 4,到 B 的权值和到 D 的权值一样大,为 3。所以该连通图有两个最小生成树:
 

三. Prim应用举例及代码实现

Prim算法解决最小生成树 (解决修路问题)Prim算法解决最小生成树 (解决修路问题)

 

 问题描述:有胜利乡有7个村庄(A, B, C, D, E, F, G) ,现在需要修路把7个村庄连通
     * 各个村庄的距离用边线表示(权) ,比如 A – B 距离 5公里。
     * 求:如何修路保证各个村庄都能连通,并且总的修建公路总里程最短? 

实现思路


         例如从A点开始,普利姆算法步骤如下:
        1.从<A>顶点开始处理,A-C [7] A-G[2] A-B[5] ,选择最小的<A,G> ,并将两点标记为已选择
       2. <A,G> 开始 , 将A 和 G 顶点和他们相邻的还没有访问的顶点进行处理 A-C[7] A-B[5]  G-B[3]             G-E[4] G-F[6]    选择最小的<A,G,B>,并标记为已选择
        3. <A,G,B> 开始,将A,G,B 顶点 和他们相邻的还没有访问的顶点进行处理 A-C[7] G-E[4] G-              F[6] B-D[9]       选择最小的<A,G,B,E>,并标记为已选择。以此类推,最后会得到:
        4.{A,G,B,E}->F//第4次大循环 ,  对应 边<E,F> 权值:5
       5.{A,G,B,E,F}->D//第5次大循环 , 对应 边<F,D> 权值:4
        6. {A,G,B,E,F,D}->C//第6次大循环 , 对应 边<A,C> 权值:7 ===> <A,G,B,E,F,D,C>
         

代码实现 

package c13prim;

import java.util.Arrays;

public class Prim {
	
	    //用一个大数表示两个点之间走不通,没有连接
	    public  static  final int N = 100;
	    
	    public static void main(String[] args) {
	        char[] vertexs = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
	        //使用数组表示邻接矩阵, N表示不连通
	        int[][] weight = new int[][]{
	                {N, 5, 7, N, N, N, 2},
	                {5, N, N, 9, N, N, 3},
	                {7, N, N, N, 8, N, N},
	                {N, 9, N, N, N, 4, N},
	                {N, N, 8, N, N, 5, 4},
	                {N, N, N, 4, 5, N, 6},
	                {2, 3, N, N, 4, 6, N}};
	 
	        Graph graph = new Graph(vertexs, weight);
            System.out.println("图的存储信息");
	        graph.showGraph();
            System.out.println("选择修建的连接边的信息");
	        graph.prim(0);
	       
	    }
	 
	    static class Graph{
	       
	        private char[] vertex;  //表示顶点信息
	        private int[][] edges;   //存放邻接矩阵 ,表示边之间的权值
	 
	        public Graph(char[] vertex,int[][] edges) {
	            this.vertex =vertex;
	            this.edges = edges;
	        }
	 
	        public void showGraph(){
	            for (int[] edge : edges) {
	                System.out.println(Arrays.toString(edge));
	            }
	        }
	 //构建Prim算法,根据思路实现代码
	        public void prim( int VertexIndex) {
	 
	            //标记顶点是否已经被选中,选中为1,没选中为0
	            int[] selected = new int[vertex.length];
	            //把当前顶点标记为已选中
	            selected[VertexIndex] = 1;
	 
	            //已经访问顶点的下标
	            int visitYesIndex = -1;
	            //还没有访问顶点的下标
	            int visitNoIndex = -1;
	            //初始化最小权值为一个不可达的数
	            int minWright = N;
	            int length=vertex.length;
	 
	 
	            //为什么从1开始?因为普利姆算法结束后,k个顶点,生成的边只能是k-1个
	            for (int k = 1; k < length; k++) {
	 
	                //每次都需要遍历已经选择的顶点,比如第一次遍历只有A点是已选择的,第二次有A,G,第三次有A,G,B,第四次......
	                for (int i = 0; i < length; i++) {
	                    //每次都需要遍历还没有被选择的顶点,比如当i 对应的为A时,j对应的有C,G,B(排除不可达的顶点)
	                    for (int j = 0; j < length; j++) {
	                        //如果i是已选择的j是未选择的且i和j之间是可达(存在边)的
	                        if (selected[i] == 1 && selected[j] == 0 && edges[i][j] < minWright) {
	                            //替换 minWeight ,寻找已经访问的顶点和没有访问的顶点的权值的最小边
	                            minWright = edges[i][j];
	                            // 替换每次比较符合条件的已选择顶点和未选择顶点
	                            visitYesIndex = i;
	                            visitNoIndex = j;
	                        }
	                    }
	                }
	                //一次循环之后  得到了最小一条边,此时要把没访问的置为已访问了
	                System.out.println("选择边 <" + vertex[visitYesIndex] + "," +vertex[visitNoIndex] + "> 权值:" + minWright);
	                selected[visitNoIndex] = 1;
	                //minWright 重新设置最大值
	                minWright = N;
	            }
	        }
	    }
	 
	}


结果展示

Prim算法解决最小生成树 (解决修路问题)

 

上一篇:图的最小生成树(prim算法和kruskal算法的实现以及讲解)


下一篇:最小生成树