Prim算法解决修路问题

今天药忘吃喽~ 2023-07-17 06:28 110阅读 0赞

**普里姆算法（Prim算法）:**

图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。

**普里姆算法和Kruskal算法的区别**  
两者都是贪心策略追求最优解,但是普里姆算法讲究**全局优先**,Kruskal算法讲究的是**局部优先**.

**普里姆算法思路**

1).输入：一个加权连通图，其中**顶点集合为V**，**边集合为E；**

2).初始化：Vnew = \{x\}，其中x为集合V中的任一节点（起始点），Enew = \{\},为空；

3).重复下列操作，直到**Vnew = V**,代表所有顶点都已经连接起来了：

a.在集合E中选取权值最小的边<u, v>，其中\*\*u为集合Vnew中的元素，而v不在Vnew集合当中，\*\*并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；

4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。

**图解:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70]  
**假设有A,B,C,D,E 5个村庄要修路使每个村子都有路连接(A->B->C也算A,C相连),但是要修路的总长度最小.**

**1.假设重A村开始选择;**

A只有3个选择,即<A,D>=5,<A,C>=7,<A,E>=10,其中**A,D之间最短所以选择A,D修路**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70 1]  
2.A,D之间修了路后A,D变成了一个整体也有3种选择即<A,C>=7,<A,E>=10,<D,B>=9,所以**应该选择路径最短的A,C**,**这就是普里姆算法体现出来的全局优先**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70 2]  
3.A,C之间修了路,A,C,C变成了一个整体,有了4种选择即<A,E>=10,<C,E>=6,<C.B>=12,<D,B>=9,**所以应该选<C,E>=6,C,E之间修路**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70 3]

4.C,E之间修路后有3中选择即<C,B>=12,<D,B>=9,<E,B>=4,所以应该在**E,B之间修路**,这时各个村庄就完全修通了.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70 4]

**完整Java代码实现**

package com.yg.algorithm;/*
    @author  Mu_Mu
    @date    2020/3/20  9:50
    */
    
    import javax.validation.constraints.Max;
    import javax.xml.crypto.Data;
    import java.util.Arrays;
    
    public class PrimAlgorithm {
        //表示不能互互通的顶点之间的距离
        private static final int MAX = 10000;
        public static void main(String[] args) {
        char []data={'A','B','C','D','E'};
        //构建顶点之间的距离
        int [][]weight={
       {MAX,MAX,7,5,10},{MAX,MAX,12,9,4},
                {7,12,MAX,MAX,6},{5,9,MAX,MAX,MAX},{10,4,6,MAX,MAX}};
            Graph graph = new Graph(data.length);
            MinTree.setGraph(graph, data.length, data, weight);
            MinTree.showGraph(graph);
            MinTree.minPath(graph,0);
        }
    
    }
    
    class MinTree {
        //构建图
        public static void setGraph(Graph graph, int verxs, char[] data, int[][] weight) {
            for (int i = 0; i < verxs; i++) {
                graph.data[i]=data[i];
                for (int j = 0; j < verxs; j++) {
                    graph.weight[i][j]=weight[i][j];
                }
            }
        }
    
        //构建最优修路路径
        //v代表从哪个顶点开始修
        public static void minPath(Graph graph,int v) {
            //用于记录哪些顶点已经被选过了
            int []visited=new int[graph.verxs];
            //表示V被选过了
            visited[v]=1;
            //表示n个顶点需要n-1条边
            for (int i = 1; i < graph.verxs; i++) {
                //最小路径
                int minPath= 10000;
                int h1=-1;//用于记录最小路劲对应的已选择过顶点的下标
                int h2=-1;//用于记录最小路劲对应的未选择过顶点的下标
                //用来每次选取距离已被选过的边这个集体最近的边,并确定路径
                for (int j = 0; j < graph.verxs; j++) {
                    for (int k = 0; k < graph.verxs; k++) {
                        if (visited[j]==1 && visited[k]==0 && graph.weight[j][k]<minPath ) {
                            minPath=graph.weight[j][k];
                            h1=j;
                            h2=k;
                        }
                    }
                }
                System.out.println("已选择顶点中" + graph.data[h1] + "与未选择顶点中"
                        + graph.data[h2] + "相连权值为" + graph.weight[h1][h2]);
                visited[h2]=1;
            }
        }
    
        //打印图
        public static void showGraph(Graph graph) {
            for (int[] w : graph.weight) {
                System.out.println(Arrays.toString(w));
            }
        }
    }
    
    class Graph {
        public int verxs=0;//顶点数
        public char []data;//顶点数据
        public int [][]weight;//表示图之间的边
    
        public Graph(int verxs) {
            this.verxs = verxs;
            data=new char[verxs];
            weight=new int[verxs][verxs];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70]: /images/20230528/db96386084c84e56ae6ae4574bb37524.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70 1]: /images/20230528/1d1cfcf946914444acd3e057f07da6c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70 2]: /images/20230528/bb03f32dd32846fb8b74b0a753edaf17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70 3]: /images/20230528/469f881cca8646a79f23e5867f0158fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70 4]: /images/20230528/834156970de24da2a9756cd9f4920b15.png