普利姆算法（Java）

快来打我* 2024-04-07 15:40 62阅读 0赞

### 第5章 普利姆算法 ###

#### 5.1 应用场景 ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mz7x8drv-1663081430708)(C:\\Users\\86139\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220913161249435.png)\]][img-mz7x8drv-1663081430708_C_Users_86139_AppData_Roaming_Typora_typora-user-images_image-20220913161249435.png]

**思路：**

尽可能的选择路径小的路线，并且每条路线权值最小，保证总里程数最小

**所以，我们必须先了解什么是最小生成树**

#### 5.2 最小生成树 ####

**基本介绍：**

1）给定一个**带权的无向连通图**，如何选取一颗生成树，使得树上所有边上权的总和为最小，这个叫最小生成树

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

3）包含全部顶点

4）N - 1 条边都在图中

5）求最小生成树的算法主要是普利姆算法和克鲁斯卡尔算法  
![在这里插入图片描述][0f19c5ff79fe47f7a3fcb0ed01558e2e.png]

#### 5.3 普利姆算法简介 ####

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

2）普利姆算法如下

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

**图解：**  
![在这里插入图片描述][53c36f34cea54eecb419af870e6f5353.png]

#### 5.4 代码实现 ####

![在这里插入图片描述][b64559f72c734e04b47d295e9fffa571.png]

package com.ldm.prim;
    
    import java.util.Arrays;
    
    /**
     * @author 梁东明
     * 2022/9/13
     * 人生建议：看不懂的方法或者类记得CTRL + 点击 看看源码或者注解
     * 点击setting在Editor 的File and Code Templates 修改
     */
    public class PrimAlgorithm {
        
        public static void main(String[] args) {
        
            //测试看看图是否创建ok
            char[] data = {
        'A','B','C','D','E','F','G'};
            int verxs = data.length;  //顶点的个数就是data的长度
            //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
            int [][]weight={
        
                    {
        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 graph = new Graph(verxs);
            //创建一个MinTree对象
            Tree tree = new Tree();
            tree.createGraph(graph, verxs, data, weight);
    
            Tree.prim(graph,0);
    
        }
    
    
    }
    
    //创建树
    class Tree{
        
        /**
         * 创建图的邻接矩阵
         *
         * @param graph    图
         * @param vertexes 顶点
         * @param data     图各个顶点的值
         * @param weight   图的邻接矩阵
         */
        public void createGraph(Graph graph,int vertexes,char[] data, int[][] weight){
        
    
            for (int i = 0; i < vertexes; i++) {
         //顶点
                graph.data[i] = data[i]; //把传进来的顶点的值赋值给图
                for (int j = 0; j < vertexes; j++) {
        
                    graph.weight[i][j] = weight[i][j]; //把传进来的邻接矩阵赋给图
                }
            }
        }
        //显示图的邻接矩阵
        public void showGraph(Graph graph){
        
            //把二维数组（邻接矩阵）的每一行输出来
            //这是增强for循环，跟普通的for循环没啥两样，就是代码简介一点而已
            for (int[]  link : graph.weight) {
        
                System.out.println(Arrays.toString(link));
            }
    
        }
        /**
         * 普利姆算法
         * 把图 转成 最小生成树
         *
         * @param graph 图
         * @param v   表示图从哪一个结点开始生成最小生成树
         */
        public static void prim(Graph graph, int v){
        
    
            int totalWeight = 0;  //记录最小生成树的总最小权值
            //创建一个数组，用来表示顶点是否被访问过，
            //1 表示已访问过  0 表示没有被访问过
            int[] isVisited = new int[graph.vertexes];
            //把传进来的第一个顶点设置为已访问
            isVisited[v] = 1;
    
            //设置两个临时变量来保存接下来循环中用到的两个顶点的下标
            int h1 = -1;
            int h2 = -1;
            //将最小值设置为10000，表示两个顶点之间没有边，二者不可达
            int minWeight = 10000;
    
            //最小生成树的一个很关键的特点
            //n个顶点的图会生成n-1 条边的最小生成树 ，所以遍历图的顶点的时候要从1开始
            for (int k = 1; k < graph.vertexes; k++) {
        
    
                //对已访问的顶点和未被访问的顶点开始for循环遍历
                for (int i = 0; i < graph.vertexes; i++) {
        //设i为已访问过的顶点
                    for (int j = 0; j < graph.vertexes; j++) {
        //设j为未被访问过的顶点
                        //graph.weight[i][j] < minWeight 两个顶点之间的边
                        //只要两个顶点只要有边，其值graph.weight[i][j]肯定小于minWeight
                        //因为初始化的minWeight为10000，超级无敌大
                        if (isVisited[i] == 1 && isVisited[j] ==0
                                && graph.weight[i][j] < minWeight){
        
                            //for循环刚开始 二者有边，它们的值就先保存下来
                            minWeight = graph.weight[i][j];
    
                            //保存二者的下标
                            h1 = i;
                            h2 = j;
                        }
                    }
                }
                totalWeight += minWeight; //每退出前面两个for循环就把minWeight保存
                System.out.println("边< " + graph.data[h1] +","+graph.data[h2] +" > 权值为： " +minWeight);
                //退出前面两个for循环之后，找到已被访问顶点和其周边未被访问的顶点的 最小权值的边
                //把未被访问的顶点设置为已被访问
                isVisited[h2] = 1;
                //将最小值设重新置为10000，方便第一个for循环重新构成最小生成树
                minWeight = 10000;
            }
            System.out.println("该最小生成树的路径为 "+totalWeight);
        }
    
    }
    
    class Graph{
        
        int vertexes;   //存放边
        char[] data;    //存放结点数据
        int[][] weight; //存放边，就是邻接矩阵
    
        public Graph(int vertexes) {
        
            this.vertexes = vertexes;
            data = new char[vertexes];
            weight = new int[vertexes][vertexes];
        }
    
    
    }

本次普利姆算法 的教程出自韩顺平的数据结构与算法

[数据结构和算法教程][Link 1]，哔哩哔哩详细教程  
在 168-171p.

最后，认识一下，我是小白。努力成为一名合格的程序员。期待与你的下次相遇。

[img-mz7x8drv-1663081430708_C_Users_86139_AppData_Roaming_Typora_typora-user-images_image-20220913161249435.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/17e47cd2e7ca432ea0944ec4020bba4d.png
[0f19c5ff79fe47f7a3fcb0ed01558e2e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/34b48fc187dc4ea380acd2113a8ff2ca.png
[53c36f34cea54eecb419af870e6f5353.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/25e124c27d5348c3bea3589948a3ff82.png
[b64559f72c734e04b47d295e9fffa571.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/e7c79901189145c19c4c54b75cec36b1.png
[Link 1]: https://www.bilibili.com/video/BV1E4411H73v?p=171&spm_id_from=pageDriver&vd_source=027fde985896626031abccc06ce8b031