当前位置: 首页 > news >正文

图——最小生成树实现(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>(){@Overridepublic 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>(){@Overridepublic 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->aif(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();}

效果:

结语:

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

相关文章:

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

目录 预备知识&#xff1a; 最小生成树概念&#xff1a; Kruskal算法&#xff1a; 代码实现如下&#xff1a; 测试&#xff1a; Prime算法 &#xff1a; 代码实现如下&#xff1a; 测试&#xff1a; 结语&#xff1a; 预备知识&#xff1a; 连通图&#xff1a;在无向图…...

Unity3D xLua开发环境搭建详解

前言 xLua是一种基于Lua语言的开发框架&#xff0c;可以帮助开发者在Unity3D中使用Lua脚本来开发游戏。 对惹&#xff0c;这里有一个游戏开发交流小组&#xff0c;希望大家可以点击进来一起交流一下开发经验呀&#xff01; 在本文中&#xff0c;我们将详细介绍如何搭建Unity…...

Python笔记-super().init(root)的作用

假设我们有一个名为Animal的父类&#xff0c;它有一个属性color&#xff0c;在其构造函数__init__中被初始化&#xff1a; class Animal:def __init__(self, color):self.color color现在&#xff0c;我们想创建一个Animal的子类&#xff0c;名为Dog。Dog类有自己的属性name&…...

【git 使用】使用 git rebase -i 修改任意的提交信息/合并多个提交

修改最近一次的提交信息的方法有很多&#xff0c;可以参考这篇文章&#xff0c;但是对于之前的提交信息进行修改只能使用 rebase。 修改提交信息 假设我们想修改下面这个提交信息&#xff0c;想把【登录】改成【退出登录】步骤如下 运行 git rebase -i head~3 打开了一个文本…...

【Vue3】toRefs和toRef在reactive中的一些应用

&#x1f497;&#x1f497;&#x1f497;欢迎来到我的博客&#xff0c;你将找到有关如何使用技术解决问题的文章&#xff0c;也会找到某个技术的学习路线。无论你是何种职业&#xff0c;我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章&#xff0c;也欢…...

力扣精选算法100道——Z字形变换(模拟专题)

目录 &#x1f388;了解题意 &#x1f388;算法原理 &#x1f6a9;先处理第一行和最后一行 &#x1f6a9;再处理中间行 &#x1f388;实现代码 &#x1f388;了解题意 大家看到这个题目的时候肯定是很迷茫的&#xff0c;包括我自己也是搞不清楚题目什么意思&#xff0c;我…...

Elastic Stack--01--简介、安装

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 1. Elastic Stack 简介为什么要学习ESDB-Engines搜索引擎类数据库排名常年霸榜![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/051342a83f574c8c910cda…...

.NET项目web自动化测试实战——Selenium 2.0

&#x1f525; 交流讨论&#xff1a;欢迎加入我们一起学习&#xff01; &#x1f525; 资源分享&#xff1a;耗时200小时精选的「软件测试」资料包 &#x1f525; 教程推荐&#xff1a;火遍全网的《软件测试》教程 &#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1…...

【Day53】代码随想录之动态规划_买卖股票ⅠⅡ

文章目录 动态规划理论基础动规五部曲&#xff1a;出现结果不正确&#xff1a; 1. 买卖股票的最佳时机2. 买卖股票的最佳时机Ⅱ 动态规划理论基础 动规五部曲&#xff1a; 确定dp数组 下标及dp[i] 的含义。递推公式&#xff1a;比如斐波那契数列 dp[i] dp[i-1] dp[i-2]。初…...

Swift Combine 使用调试器调试管道 从入门到精通二十六

Combine 系列 Swift Combine 从入门到精通一Swift Combine 发布者订阅者操作者 从入门到精通二Swift Combine 管道 从入门到精通三Swift Combine 发布者publisher的生命周期 从入门到精通四Swift Combine 操作符operations和Subjects发布者的生命周期 从入门到精通五Swift Com…...

go内置库函数实现client与server数据的发送接收

功能&#xff1a;客户端持续写入数据&#xff0c;直到输入exit退出&#xff0c;服务端读取数据并打印 注意&#xff1a;server和client目录在同一层级 服务端 server/main package mainimport ("fmt""net" )func main() {listen, err : net.Listen(&quo…...

[java基础揉碎]this

引出this: 什么是this: java虚拟机会给每个对象分配 this&#xff0c;代表当前对象。 这里的this就是new出来的这个对象 this的本质: this是个引用在堆中指向它自己: this的细节: 访问成员方法: 访问构造器:...

vulnhub靶场之Deathnote

一.环境搭建 1.靶场描述 Level - easy Description : dont waste too much time thinking outside the box . It is a Straight forward box . This works better with VirtualBox rather than VMware 2.靶场下载 https://www.vulnhub.com/entry/deathnote-1,739/ 3.启动环…...

Docker安装Postgresql12

1、搜索仓库中postgres docker search postgres 2、拉取镜像 docker pull postgres docker pull postgres:12 #拉取12版本的PG库 3、创建数据库文件夹 cd /temp/ && mkdir -m 755 postgres-data 注&#xff1a;-m表示权限&#xff0c;类chmod命令 4、执行命令启动…...

服务器防火墙的应用技术有哪些类型?

随着互联网的发展&#xff0c;网络安全问题更加严峻。服务器防火墙技术作为一种基础的网络安全技术&#xff0c;对于保障我们的网络安全至关重要。本文将介绍服务器防火墙的概念和作用&#xff0c;以及主要的服务器防火墙技术&#xff0c;包括数据包过滤、状态检测、代理服务、…...

IP地理位置查询定位:技术原理与实际应用

在互联网时代&#xff0c;IP地址是连接世界的桥梁&#xff0c;而了解IP地址的地理位置对于网络管理、个性化服务以及安全监控都至关重要。IP数据云将深入探讨IP地理位置查询定位的技术原理、实际应用场景以及相关的隐私保护问题&#xff0c;旨在为读者提供全面了解和应用该技术…...

hbuilder运行不了php文件是什么原因?

如果 HBuilder 无法运行 PHP 文件&#xff0c;可能是由于以下几个常见原因导致的&#xff1a; 未安装 PHP 解释器&#xff1a; HBuilder 需要安装 PHP 解释器才能运行 PHP 文件。请确保您的系统中已经安装了 PHP&#xff0c;并且已正确配置了环境变量。 PHP 解释器路径错误&…...

C++从入门到精通 第十六章(STL常用算法)

写在前面&#xff1a; 本系列专栏主要介绍C的相关知识&#xff0c;思路以下面的参考链接教程为主&#xff0c;大部分笔记也出自该教程&#xff0c;笔者的原创部分主要在示例代码的注释部分。除了参考下面的链接教程以外&#xff0c;笔者还参考了其它的一些C教材&#xff08;比…...

【海贼王的数据航海:利用数据结构成为数据海洋的霸主】时间复杂度 | 空间复杂度

目录 1 -> 算法效率 1.1 -> 如何衡量一个算法的好坏&#xff1f; 1.2 -> 算法的复杂度 2 -> 时间复杂度 2.1 -> 时间复杂度的概念 2.2 -> 大O的渐进表示法 2.3 -> 常见时间复杂度计算 3 -> 空间复杂度 4 -> 常见复杂度对比 1 -> 算法效…...

OpenTiny Vue 组件库适配微前端可能遇到的4个问题

本文由体验技术团队 TinyVue 项目成员岑灌铭同学创作。 前言 微前端是一种多个团队通过独立发布功能的方式来共同构建现代化 web 应用的技术手段及方法策略&#xff0c;每个应用可以选择不同的技术栈&#xff0c;独立开发、独立部署。 TinyVue组件库的跨技术栈能力与微前端十…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...