• 普利姆算法(Java)


    第5章 普利姆算法

    5.1 应用场景

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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)求最小生成树的算法主要是普利姆算法和克鲁斯卡尔算法
    在这里插入图片描述

    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 条边

    图解:
    在这里插入图片描述

    5.4 代码实现

    在这里插入图片描述

    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];
        }
    
    
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136

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

    数据结构和算法教程,哔哩哔哩详细教程
    在 168-171p.

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

  • 相关阅读:
    蓄电池为什么要巡检?智能电池巡检箱监控系统方案帮您解答
    【BOOST C++ 17 出错处理】(2)Boost.System
    30岁之前一定要明白的道理
    分享程序员面试的7个技巧
    怎么将视频转换成mp4?
    家政预约服务APP小程序搭建,功能支持定制
    开源原生android的视频编辑软件
    Promise异步编程
    Flink CEP 超时事件处理:使用侧输出流和 Scala Lambda 版本编程
    android 9 adb安装过程学习(一)
  • 原文地址:https://blog.csdn.net/weixin_48544279/article/details/126843573