图——最小生成树实现(Kruskal算法,prime算法)

目录

预备知识:

最小生成树概念:

Kruskal算法:

代码实现如下:

测试:

Prime算法 :

代码实现如下:

测试:

结语:


预备知识:

连通图:在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与顶点v2是连通的。如果图中任意一 对顶点 都是连通的,则称此图为连通图。

生成树:一个连通图的生成树是指一个连通子图,它含有图中全部n个顶点,但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边,如果生成树中再添加一条边,则必定成环。

并查集:

由于本文章重点不在讲述并查集,故下面我简单描述并查集的作用,各种方法,源码如下。

并查集的作用:可以将一个数组中的元素分为多个小组的数据结构。

方法:

findRoot(x):查找x的根。

union(int x1, int x2):合并x1和x2。

isSameSet(int x1, int x2):判断两个数字 是不是在同一个集合当中。

import java.util.Arrays;

public class UnionFindSet {
    private int[] elem;//底层是数组
    public UnionFindSet(int n){
        this.elem = new int[n];
        Arrays.fill(elem,-1);//整体初始化为-1:代表根
    }

    /**
     * 查找x的根
     * @param x
     * @return
     */
    public int findRoot(int x){
        if(x < 0){
            throw new IndexOutOfBoundsException("数据不合法");
        }
        while(elem[x] >= 0){
            x = elem[x];
        }
        return x;
    }

    /**
     * 合并x1和x2
     * @param x1
     * @param x2
     */
    public void union(int x1,int x2){
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if(index1 == index2){//说明x1和x2的根是相同的,不需要进行合并
            return;
        }
        elem[index1] = elem[index1] + elem[index2];
        elem[index2] = index1;//将x2合并到x1
    }

    /**
     * 判断两个数字是不是在同一个集合当中
     * @param x1
     * @param x2
     * @return
     */
    public boolean isSameSet(int x1,int x2){
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if(index1 == index2){
            return true;
        }else{
            return false;
        }
    } 
}

最小生成树概念:

连通图中的每一棵生成树,都是原图的一个极大无环子图,即:从其中删去任何一条边,生成树 就不在连通;反之,在其中引入任何一条新边,都会形成一条回路。

若连通图由n个顶点组成,则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三 条:

(1) 只能使用图中的边来构造最小生成树。

(2) 只能使用恰好n-1条边来连接图中的n个顶点。

(3) 选用的n-1条边不能构成回路。

构造最小生成树的方法:Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。

贪心算法:是指在问题求解时,总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的选择,而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。

Kruskal算法:

Kruskal算法采用全局贪心的策略,其步骤如下:

任给一个有n个顶点的连通网络N={V,E}。

(1)首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL},其中每个顶点自成一个连通分量。

(2)其次不断从E中取出权值最小的一条边(若有多条任取其一),若该边的两个顶点来自不同的连通分量(若相同则不加因为会生成环),则将此边加入到G中。

(3)如此重复,直到所有顶点在同一个连通分量上为止。

核心:每次迭代时,选出一条具有最小权值,且两端点不在同一连通分量上的边,加入生成树。

 具体过程如下图所示:按照abc..的循序,箭头为当前要操作的位置(不一定能添加,黑色为可添加)。

  

代码实现如下:

先构造关于Edge的小根堆,由于是自定义类,故要自己实现一个比较器Comparator。

1. 定义优先级队列存储边构建小根堆 跟进权重进行比较。

2. 把矩阵当中的边全部入队列。

3. 定义并查集判断将来两条边是不是在一个集合(避免构成环)。

4. 由于篇幅有限matrix之类的前文实现过这里不在实现有需要的友友可以前往图的概念

static class Edge{
        public int srcIndex;
        public int destIndex;
        public int weight;
        public Edge(int srcIndex,int destIndex,int weight){
            this.srcIndex = srcIndex;
            this.destIndex = destIndex;
            this.weight = weight;
        }
    }
    public int kruskal(GraphByMatrix minTree){
        //1. 定义优先级队列 存储边 构建小根堆 跟进权重进行比较
        PriorityQueue<Edge> minHeap = new PriorityQueue<>(new Comparator<Edge>(){
            @Override
            public int compare(Edge o1,Edge o2){
                return o1.weight - o2.weight;
            }
        });
        int n = matrix.length;
        //2. 把矩阵当中的边全部入队列
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                //因为是无向图,所以只入一半就可以 i < j 即可
                if(i < j && matrix[i][j] != Integer.MAX_VALUE){
                    Edge edge = new Edge(i,j,matrix[i][j]);
                    minHeap.offer(edge);
                }
            }
        }
        //3、最后整个的权重
        int totalWeight = 0;
        int size= 0;
        //4.定义并查集 判断将来两条边 是不是在一个集合
        UnionFindSet ufs = new UnionFindSet(n);
        //5. 出优先级队列的n-1条边
        while(size < n-1 &&!minHeap.isEmpty()){
            Edge min  = minHeap.poll();
            int srcIndex = min.srcIndex;
            int destIndex = min.destIndex;
            //判断是不在在同一个集合当中,在一个集合 就不能添加
            if(!ufs.isSameSet(srcIndex,destIndex)){
                //打印选出的边
                System.out.println("选择的边: "+ arrayV[srcIndex] + "-> "+ arrayV[destIndex] + ":"+
                matrix[srcIndex][destIndex]);
                ?
                minTree.addEdgeUseIndex(srcIndex,destIndex,min.weight);
                totalWeight += min.weight;
                //添加完成之后,说明 可以 合并到同一个集合
                ufs.union(srcIndex,destIndex);
                size++;
            }
        }
        //如果是 选出n-1条边,否则就说明不是连通图
        if(size == n-1){
            return totalWeight;
        }
        //不是连通图, 可能选不出n-1条边  假设一个图中,有其他的顶点独立着
        return -1;
    }
    private void addEdgeUseIndex(int srcIndex,int destIndex,int weight) {
        matrix[srcIndex][destIndex] = weight;
        //如果是无向图 那么相反的位置 也同样需要置为空
        if(!isDirect) {
            matrix[destIndex][srcIndex] = weight;
        }
    }

测试:

测试代码对应的图:

测试代码 :

public static void main(String[] args) {
        testGraphMinTreeKruskal();
    }
    public static void testGraphMinTreeKruskal() {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),false);
        g.initArrayV(array);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
        //g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        GraphByMatrix  kminTree = new GraphByMatrix(str.length(),false);
        System.out.println(g.kruskal(kminTree));
        kminTree.printGraph();
    }

效果:

显然正确💯

Prime算法 :

Primel算法采用局部贪心的策略,其步骤如下:

按照字母顺序abc....看。

代码实现如下:

由于是局部贪心用两个Set,那么天然就不会有环,故prime可以不用并查集。

1. 先获取当前顶点的下标。

2. 定义一个X集合,把当前的起点下标存进去。

3. 定义一个Y集合,存储目标顶点的元素。

4. 除了刚刚的起点,其他的顶点需要放到Y。

5. 从X集合中的点到Y集合的点中,连接的边中找出最小值放到优先级队列。

6. 把当前顶点连接出去的所有的边放入队列。

7.把这次的目标点,添加到X集合,变成了起点记得把之前的目标点,从Y集合删除掉。

8.遍历刚刚添加的新起点destIndex,连接出去的所有边,再次添加到优先级队列。

public int prim(GraphByMatrix minTree,char chV){
        //1. 先获取当前顶点的下标
        int srcIndex = getIndexOfV(chV);
        int n = arrayV.length;
        //2. 定义一个X集合,把当前的起点下标存进去
        Set<Integer> setX = new HashSet<>();
        //3. 定义一个Y集合,存储目标顶点的元素
        Set<Integer> setY = new HashSet<>();
        setX.add(srcIndex);
        //4. 除了刚刚的起点,其他的顶点需要放到Y集合
        for(int i = 0;i < n;i++){
            if(i != srcIndex){
                setY.add(i);
            }
        }
        //5. 从X集合中的点到Y集合的点中,连接的边中找出最小值放到优先级队列
        PriorityQueue<Edge> minHeap = new PriorityQueue<>(new Comparator<Edge>(){
            @Override
            public int compare(Edge o1,Edge o2){
                return o1.weight - o2.weight;
            }
        });
        //6. 把当前顶点连接出去的所有的边放入队列
        for(int i = 0;i < n;i++){
            if(matrix[srcIndex][i] != Integer.MAX_VALUE){
                minHeap.offer(new Edge(srcIndex,i,matrix[srcIndex][i]));
            }
        }
        int size = 0;
        int totalWeight = 0;
        while(size < n - 1 && !minHeap.isEmpty()){
            //7. 取出队列中的第一条边
            Edge min = minHeap.poll();
            int srcI = min.srcIndex;
            int destI = min.destIndex;
           //起始点本身就在X集合,所以这里只需要判断目标点即可
            if(setX.contains(destI)){
                //包含
            }else{
                //8. 直接将该边 放入最小生成树
                minTree.addEdgeUseIndex(srcI,destI,min.weight);
                //9. 每选一条边 就打印一条语句
                System.out.println("选择的边: "+ arrayV[srcI] + "-> "+ arrayV[destI] + ":"+
                        matrix[srcI][destI]);
                size++;
                totalWeight += min.weight;
                //10.把这次的目标点,添加到X集合,变成了起点
                setX.add(destI);
                //11.记得把之前的目标点,从Y集合删除掉
                setY.remove(destI);
                //12. 遍历刚刚添加的新起点destIndex,连接出去的所有边,再次添加到优先级队列
                for(int i = 0;i < n;i++){
                    // 13. !setX.contains(i) 判断目标点不能再X这个集合 例如: a->b 就包含了b->a
                    if(matrix[destI][i] != Integer.MAX_VALUE && !setX.contains(i)){
                        minHeap.offer(new Edge(destI,i,matrix[destI][i]));
                    }
                }
            }
        }
        if(size == n-1){
            return totalWeight;
        }else{
            return -1;
        }
    }

测试:

测试对应的图:

测试代码 :

public static void main(String[] args) {
        testGraphMinTreePrime();
    }
    public static void testGraphMinTreePrime() {
        String str = "abcdefghi";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(), false);
        g.initArrayV(array);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
        //g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        GraphByMatrix primTree = new GraphByMatrix(str.length(), false);
        System.out.println(g.prim(primTree, 'a'));
        primTree.printGraph();
    }

效果:

结语:

其实写博客不仅仅是为了教大家,同时这也有利于我巩固自己的知识点,和一个学习的总结,由于作者水平有限,对文章有任何问题的还请指出,接受大家的批评,让我改进,如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注,这可以激励我写出更加优秀的文章。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/402212.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

前缀和第二弹

力扣560.和为k的子数组 子数组经典暴力解法&#xff1a;枚举全部位置&#xff0c;因为取值为可能为负 首先把前缀和&#xff0c;和出现的次数都存储一下&#xff0c;一般前缀和就出现一次&#xff0c;然后往后找&#xff0c;如果前缀和-k就说明有一段数组是等于sum-k class Sol…

Python 如何给出一个周期性函数接近某个值所有的值

Python 如何给出一个周期性函数接近某个值的值 推荐阅读正文一般化周期性函数拓展推荐阅读 Python 寻找一个一维数组中最接近某个值的元素 Python 如何切分函数 正文 一般化周期性函数 本文一看,可能感觉标题有些拗口,难以理解,请看下图: 图像显然具有一定的周期性,如…

特殊文本文件

特殊文件 普通文件.txt属性文件.propertiesXML文件.xml 为什么要用这些特殊文件 存储多个用户的&#xff1a;用户名、密码 存储多个用户的&#xff1a;用户名、密码、家乡、性别 存储有关系的数据&#xff0c;做完系统的配置文件 做为信息进行传输 这些特殊文件&#xff0c;我…

Android中通过属性动画实现文字轮播效果

前些天发现了一个蛮有意思的人工智能学习网站,8个字形容一下"通俗易懂&#xff0c;风趣幽默"&#xff0c;感觉非常有意思,忍不住分享一下给大家。 &#x1f449;点击跳转到教程 一、创建一个自定义ProvinceView类,具体代码如下 /*** Author: ly* Date: 2024/2/22* D…

Redis的常见面试题

目录 前言 Redis支持哪些数据类型 五种核心类型 Zset为什么用跳表不用红黑树 &#xff1f; Redis常见的应用场景&#xff1f; 如何检测Redis的连通性&#xff1f; 如何设置key的过期时间&#xff1f; Redis为什么是单线程模型&#xff1f; Redis里的IO多路复用是什…

恶意代码识别率提升95%!谷歌开源人工智能网络安全防御工具

近日&#xff0c;谷歌日前宣布发起网络安全人工智能防御计划&#xff0c;旨在利用人工智能技术提升网络安全水平&#xff0c;扭转困扰网络安全行业的“防守困境”。 该计划的核心举措是开源Magika&#xff0c;这是一款用于文件类型识别的AI工具&#xff0c;能够帮助检测恶意软件…

国产嵌入式教学实验箱操作教程:2-13 定时器控制实验

一、实验目的 熟悉定时器的基本结构&#xff0c;学习定时器的功能和控制方法&#xff0c;并实现基于定时器中断方式控制程序。 二、实验原理 定时器 TMS320CC6748有4个定时器/计数器&#xff0c;均可配置为64位计数器、两个独立32位计数器及自动重装32位计数器&#xff0c;…

【FreeRTOS基础入门】事件组与同步点

文章目录 前言一、事件组是什么案例1.1 事件组的概念 二、事件组的操作2.1 事件组与其他实现同步与互斥方法的区别2.2 创建事件组2.3 删除事件组2.4 设置事件2.5 等待事件2.6 示例代码 三、同步点3.1 同步点是什么3.2 设置同步点 总结 前言 FreeRTOS是一个广泛应用于嵌入式系统…

我的第一个浏览器插件网页一键上传的开发历史

前言 一键上传选中的网页内容&#xff0c;实现知识快速收藏。如飞书剪存&#xff0c;有道云剪报&#xff0c;MrDoc速记。早在2008年&#xff0c;我参考了有道云一键上传&#xff0c;实现了一个简单的浏览器插件&#xff0c;能方便保存网页内容到个人网站。这些插件目前都很难兼…

Day32 进程Process

文章目录 1.什么是进程1.1 概念1.2 特点1.3 进程段1.4 进程分类1.5 进程状态1.6 进程状态切换图1.7 调度进程 2.进程函数接口2.1 创建进程 fork()2.2 回收资源函数2.3 结束进程2.4 获取进程号 3.exec函数族&#xff08;了解&#xff09;4.守护进程 Daemon4.1 守护进程的特点4.2…

提升技术栈的秘诀:Spring Cloud学习网站带你飞跃职业瓶颈!

介绍&#xff1a;Spring Cloud是一个基于Spring Boot实现的微服务架构开发工具集。 Spring Cloud利用Spring Boot的开发便利性简化了分布式系统基础设施的开发。例如&#xff0c;服务发现注册、配置中心、消息总线、负载均衡、断路器、数据监控等都是其内置的功能。它的优势包括…

LangChain支持哔哩哔哩视频总结

是基于LangChain框架下的开发&#xff0c;所以最开始请先 pip install Langchain pip install bilibili-api-python 技术要点&#xff1a; 使用Langchain框架自带的Document loaders 修改BiliBiliLoader的源码&#xff0c;自带的并不支持当前b站的视频加载 源码文件修改&a…

前端架构: 实现脚手架终端UI样式之ANSI escape code, Chalk, Ora介绍

在脚手架当中实现命令行的UI显示 1 &#xff09;概述 在命令行中&#xff0c;如果想实现除传统的常规文本以外的内容比如想对字体进行加粗斜体下划线&#xff0c;包括对它改变颜色改变前景色改变后景色等等需要借助一个叫做 ANSI escape code 这样的一个概念它其实是一个标准&…

文献速递:GAN医学影像合成--基于生成对抗网络的肺部图像分类的多域医学图像翻译生成

文献速递&#xff1a;GAN医学影像合成–基于生成对抗网络的肺部图像分类的多域医学图像翻译生成 01 文献速递介绍 在2019年底&#xff0c;一种称为2019冠状病毒病&#xff08;COVID-19&#xff09;的新型冠状病毒肺炎出现&#xff0c;迅速成为全球性大流行。感染COVID-19可以…

18.贪心算法

排序贪心 区间贪心 删数贪心 统计二进制下有多少1 int Getbit_1(int n){int cnt0;while(n){nn&(n-1);cnt;}return cnt; }暴力加一维前缀和优化 #include <iostream> #include <climits> using namespace std; #define int long long const int N2e510; in…

热门游泳耳机哪个牌子好,吐血整理全网高口碑机型!

近年来&#xff0c;游泳已经成为众多人们喜爱的运动项目之一。而在游泳过程中&#xff0c;许多人希望能够享受到音乐的陪伴&#xff0c;以增加运动的乐趣。然而&#xff0c;由于阻力、防水和水压等问题&#xff0c;传统的耳机并不能满足游泳者的需求。因此&#xff0c;在市面上…

基于JAVA+SpringBoot+Vue的前后端分离的电子商城

✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取项目下载方式&#x1f345; 一、项目背景介绍&#xff1a; 在当今数字化时代&…

bat判断vmware 是否已安装

要通过批处理脚本&#xff08;.bat&#xff09;判断VMware是否已安装&#xff0c;您可以尝试以下方法&#xff1a; 检查VMware的进程 您可以检查VMware相关的进程是否在运行。例如&#xff0c;VMware Workstation的进程名通常是vmware-workstation.exe。 echo off tasklist /…

计网 - 域名解析的工作流程

文章目录 Pre引言1. DNS是什么2. 域名结构3. 域名解析的工作流程4. 常见的DNS记录类型5. DNS安全6. 未来的发展趋势 Pre 计网 - DNS 域名解析系统 引言 在我们日常使用互联网时&#xff0c;经常会输入各种域名来访问网站、发送电子邮件或连接其他网络服务。然而&#xff0c;我…

【命令行工具kubectl】

如何在k8s的任意节点使用用kubectl # 正常在node节点上是无法执行kubectl命令 [rootk8s-node-01 ~]# kubectl get pods The connection to the server localhost:8080 was refused - did you specify the right host or port?1、将master节点中/etc/kubernetes/,admin.conf拷…