普利姆算法和修路问题

喜欢ヅ旅行 2023-07-13 03:50 40阅读 0赞

### 修路问题 ###

看一个应用场景和问题：  
![在这里插入图片描述][20200310120215757.png]

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

思路: 将10条边，连接即可，但是总的里程数不是最小.  
正确的思路：就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少

### 普利姆算法 ###

修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称MST。  
要理解普利姆算法，必须理解和学过数据结构 - [图][Link 1]

1.  给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
2.  N个顶点，一定有N-1条边
3.  包含全部顶点
4.  N-1条边都在图中
5.  举例说明(如图:)
6.  求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70]

*  **普利姆算法介绍**

1.  普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图
2.  普利姆的算法如下:

> 1.  设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合
> 2.  若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited\[u\]=1
> 3.  若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边（ui,vj）加入集合D中，标记visited\[vj\]=1
> 4.  重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边

单独看上面步骤很难理解普利姆算法

>  *  其实对上面的步骤可以这样理解普利姆算法，就是从一个图中选取一个顶点
> 
> 1.  然后以这个顶点开始，寻找**与这个顶点连接的所有边中最小的那个边**
> 2.  然后从找到的这个最小的边2个顶点开始，继续寻找他们所有的边(排除已经找到的边)，直到找的到另最小的边，
> 3.  如此循环这样的步骤，直到找n-1个边 （n表示顶点的个数）

如还不理解，看下面图解普利姆算法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 1]

*  **代码实践**

修路问题：  
![在这里插入图片描述][20200310122515631.png]

代码如下：  
1.先定义一个图类(Graph)

// 图
    public class Graph { 
        // 图的顶点
        private char[] vertex;
        // 图的边，邻接矩阵表示
        private int[][] weight;
    
        public Graph(char[] vertex, int[][] weight) { 
            this.vertex = vertex;
            this.weight = weight;
        }
    
        public char[] getVertex() { 
            return vertex;
        }
    
        public void setVertex(char[] vertex) { 
            this.vertex = vertex;
        }
    
        public int[][] getWeight() { 
            return weight;
        }
    
        public void setWeight(int[][] weight) { 
            this.weight = weight;
        }
    }

2.在定义一个类边（Edge），用来描述2个村庄之间的路

// 边
    public class Edge { 
        // 边的开始顶点
        char start;
        // 边的另一个顶点
        char end;
        // 边的权
        int weight;
    
        public Edge(char start, char end, int weight) { 
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    
        @Override
        public String toString() { 
            return "Edge{" +
                    "start=" + start +
                    ", end=" + end +
                    ", weight=" + weight +
                    '}';
        }
    }

3.定义最小生成树类，里面有**普利姆算法方法**

/** * 最小生成树 */
    public class MinTree { 
    
        public List<Edge> prim(Graph graph) { 
            return prim(graph, 0);
        }
    
        /** * 普利姆算法 * @param index 最开始访问顶点的下标 * @param graph 村庄图 * @return 返回最小生成树的最小边的集合 */
        private List<Edge> prim(Graph graph, int index) { 
            if (graph == null) { 
                return null;
            }
            List<Edge> edgeList = new ArrayList<>();
    
            // 获取图的顶点数组
            char[] vertex = graph.getVertex();
            // 获取图的边，邻接矩阵
            int[][] weight = graph.getWeight();
            // 定义一个数组，记录已访问顶点的下标
            int[] visitied = new int[vertex.length];
            // 先把index加入到visitied数组，表示已访问过
            visitied[index] = 1;
    
            // 该第一个for循环表示：一次循环结束，表示找到一个最小距离顶点，和一条最短的边
            for (int i = 0; i < vertex.length; i++) { 
                // 定义一个遍历，用来记录遍历过程中找到的最小边的权值，初始化10000，
                int minWeight = 10000;
                // 定义变量a,b，用来记录找到的顶点
                int a = -1;
                int b = -1;
                // 定义一个边用来记录找到的边
                // 下面2个嵌套for循环表示找最小边，和顶点,(相当于遍历邻接矩阵寻找最小边)
                for (int m = 0; m < vertex.length; m++) { 
                    for (int n = 0; n < vertex.length; n++) { 
                        // visitied[m] == 1表示下标为m的顶点已经访问过，并且找到以该顶点相关的边最小的边
                        if (visitied[m] == 1 && visitied[n] !=1 && weight[m][n] < minWeight) { 
                            minWeight = weight[m][n];
                            a = m;
                            b = n;
                        }
                    }
                }
    
                if (minWeight != 10000 && a != -1 && b != -1) { 
                    // 把该顶点加入到已访问的数组中,不加入a是因为，a已经加入过了
                    visitied[b] = 1;
                    // 说明找到了一个最小边
                    Edge edge = new Edge(vertex[a],vertex[b], minWeight);
                    // 加入到集合
                    edgeList.add(edge);
                }
            }
            return edgeList;
        }
    }

测试类，有初始化图

public class MyTest { 
        public static void main(String[] args) { 
            // 初始化村庄的图
            //测试看看图是否创建ok
            char[] data = new char[]{ 'A','B','C','D','E','F','G'};
            int verxs = 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},};
            // 初始化图
            Graph graph = new Graph(data, weight);
    
            MinTree minTree = new MinTree();
            // 调用普利姆算法，获取最小边的集合
            List<Edge> edgeList = minTree.prim(graph);
            System.out.println(edgeList.toString());
        }
    }

运行结果：  
可以得到一个封装了边的list集合，就是普利姆算法的最小生成的边

[Edge{ start=A, end=G, weight=2}, Edge{ start=G, end=B, weight=3}, Edge{ start=G, end=E, weight=4}, Edge{ start=E, end=F, weight=5}, Edge{ start=F, end=D, weight=4}, Edge{ start=A, end=C, weight=7}]

上面代码中，普利姆算法的核心代码是如这个3层嵌套for循环，注意理解这个3层嵌套for循环的意思，都有详细注释，理解普利姆算法的思想

// 该第一个for循环表示：一次循环结束，表示找到一个最小距离顶点，和一条最短的边
            for (int i = 0; i < vertex.length; i++) { 
                // 定义一个遍历，用来记录遍历过程中找到的最小边的权值，初始化10000，
                int minWeight = 10000;
                // 定义变量a,b，用来记录找到的顶点
                int a = -1;
                int b = -1;
                // 定义一个边用来记录找到的边
                // 下面2个嵌套for循环表示找最小边，和顶点,(相当于遍历邻接矩阵寻找最小边)
                for (int m = 0; m < vertex.length; m++) { 
                    for (int n = 0; n < vertex.length; n++) { 
                         // visitied[m] == 1表示下标为m的顶点已经访问过，visitied[n] !=1表示下标为n的顶点没有访问过
                        // 并且找到以该顶点相关的边最小的边
                        if (visitied[m] == 1 && visitied[n] !=1 && weight[m][n] < minWeight) { 
                            minWeight = weight[m][n];
                            a = m;
                            b = n;
                        }
                    }
                }

[20200310120215757.png]: https://img-blog.csdnimg.cn/20200310120215757.png
[Link 1]: https://blog.csdn.net/fyj13925475957/article/details/104709851
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200310120504375.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200310122333196.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70
[20200310122515631.png]: https://img-blog.csdnimg.cn/20200310122515631.png