Java实现之普利姆(Prim)算法

蔚落 2024-04-01 18:34 65阅读 0赞

## 一.问题引入 ##

### 1.问题引入 ###

![de3d8fe08d4841189f90c0ab34a03028.png][]

1)有胜利乡有7个村庄(A, B,C,D,E,F,G)，现在需要修路把7个村庄连通

2)各个村庄的距离用边线表示(权)，比如A-B距离5公里

3)问:如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?

### 2.最小生成树 ###

修路问题本质就是就是最小生成树问题，先介绍一下**最小生成树(Minimum Cost Spanning Tree)**，简称MST.  
1） 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为  
最小,这叫最小生成树

2)N个顶点，一定有N-1条边

3)包含全部顶点

4)N-1条边都在图.

5)举例说明(如图)

6)求最小生成树的算法主要是普里姆  
算法和克鲁斯卡尔算法

![3228a015016740d397db84800effab93.png][]

## 二.普利姆算法 ##

### 1.基本介绍 ###

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条边  
(5)提示:单独看步骤很难理解，我们通过代码来讲解，比较好理解.

### 2.算法图解 ###

1.从<A>顶点开始处理======><A,G>

A-C\[7\] A-G\[2\] A-B\[5\]  
2.<A,G>开始,将A和G顶点和他们相邻的还没有访问的顶点进行处理=====><A,G,B>

A-C\[7\] A-B\[5\] G-B\[3\] G-E\[4\] G-F\[6\]  
3.<4,G,B>开始，将A,G,B顶点和他们相邻的还没有访问的顶点进行处理====><A,G,B,E>

A-C\[7\] G-E\[4\] G-F\[6\] B-D\[9\]

![ef293e85a656462ba4bd6f7d7befc92d.png][]

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\}

### 3.代码实现 ###

public class Prim {
        public static void main(String[] args) {
            char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
            int vertex = data.length;
            //邻接矩阵的关系用二维数组表示,其中Integer.MAX_VALUE表示不连通
            int[][] weight = new int[][]{
                    {Integer.MAX_VALUE, 5, 7, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 2},
                    {5, Integer.MAX_VALUE, Integer.MAX_VALUE, 9, Integer.MAX_VALUE, Integer.MAX_VALUE, 3},
                    {7, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 8, Integer.MAX_VALUE, Integer.MAX_VALUE},
                    {Integer.MAX_VALUE, 9, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 4, Integer.MAX_VALUE},
                    {Integer.MAX_VALUE, Integer.MAX_VALUE, 8, Integer.MAX_VALUE, Integer.MAX_VALUE, 5, 4},
                    {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 4, 5, Integer.MAX_VALUE, 6},
                    {2, 3, Integer.MAX_VALUE, Integer.MAX_VALUE, 4, 6, Integer.MAX_VALUE}
            };
            MGraph graph = new MGraph(vertex, data, weight);
    
            prim(graph, 0);
    
    
        }
    
        /**
         * @param graph 图
         * @param v     表示从图的第几个顶点开始生成
         */
        public static void prim(MGraph graph, int v) {
            //标记结点是否访问过了,默认false,表示没有访问过
            boolean[] isVisted = new boolean[graph.vertex];
            isVisted[v] = true;
            //index1和index2为两个顶点的下标
            int index1 = -1, index2 = -1;
            //将初始最小权重为最大值
            int minWeight = Integer.MAX_VALUE;
    
            for (int k = 1; k < graph.vertex; ++k) {
                for (int i = 0; i < graph.vertex; ++i) {
                    for (int j = 0; j < graph.vertex; ++j) {
                        if (isVisted[i] && !isVisted[j] && graph.weight[i][j] < minWeight) {
                            minWeight = graph.weight[i][j];
                            index1 = i;
                            index2 = j;
                        }
    
                    }
    
                }
                //找到的一条最小的边
                System.out.println("边<" + graph.data[index1] + "," + graph.data[index2] + ">  weight:" + minWeight);
                isVisted[index2] = true;
                minWeight = Integer.MAX_VALUE;
    
            }
    
    
        }
    }
    
    class MGraph {
        int vertex;  //表示图的结点个数
        char[] data;  //保存结点的数据
        int[][] weight; //存放边,就是邻接矩阵
    
        public MGraph() {
        }
    
        public MGraph(int vertex, char[] data, int[][] weight) {
            this.vertex = vertex;
            this.data = data;
            this.weight = weight;
        }
    
        public void showGraph() {
            for (int[] ints : weight) {
                System.out.println(Arrays.toString(ints));
            }
        }
        //编写prim算法,得到最小生成树
    
    
    }

[de3d8fe08d4841189f90c0ab34a03028.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ca55222588c840ec995f11426f80255f.png
[3228a015016740d397db84800effab93.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3de5cdbc3b6c431da8c943201e42f8c4.png
[ef293e85a656462ba4bd6f7d7befc92d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/966730f436b44f069be6aef442a434db.png