图论中的最小生成树:Kruskal与Prim算法深入解析

 

                                               🎬慕斯主页修仙—别有洞天

                                              ♈️今日夜电波:アンビバレント—Uru

                                                                0:24━━━━━━️💟──────── 4:02
                                                                    🔄   ◀️   ⏸   ▶️    ☰  

                                      💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍


 

目录

最小生成树

Kruskal算法

如何理解Kruskal算法?

Kruskal算法的实现

Prim算法

如何理解Prim算法?

Prim算法的实现


最小生成树

        最小生成树(Minimum Spanning Tree,简称 MST)是一个无向连通图中包含所有顶点的边的权值之和最小的子图。它有以下特点:

  1. 包含原图所有顶点:最小生成树是一个生成树,因此它必须包含图中的所有顶点。
  2. 边的权值之和最小:在所有的生成树中,最小生成树是边的权值总和最小的那一个。
  3. 是无环的:作为一棵树,最小生成树中不存在环,即任意两个顶点之间有且仅有一条路径相连。

        求解最小生成树的常用算法有两种:

  • Kruskal算法:该算法的基本思想是按照边的权值从小到大的顺序选择边,如果这条边连接的两个顶点不在同一个连通分量中,则加入这条边,直到所有顶点都被包含在内。这个过程中,使用并查集数据结构来判断两个顶点是否属于同一个连通分量是非常有效的。
  • Prim算法:与Kruskal算法不同,Prim算法是一种贪心算法,它从任意一个顶点开始,每一步都选择连接当前已选取顶点集合与未选取顶点集合之间权值最小的边,并将其加入到最小生成树中,直到所有顶点都被包含。

        总的来说,最小生成树的概念在许多领域都有应用,如网络设计、交通规划等,它可以帮助找到成本最低的连接方案。

Kruskal算法

如何理解Kruskal算法?

        Kruskal算法是一种用来寻找最小生成树的贪心算法,它的核心思想是选择边权值之和最小的同时不会形成环路的边来构建最小生成树。(使用的就是全局的贪心策略)具体步骤如下:

  1. 边的排序:将图中的所有边按照权值从小到大进行排序。(这一步我们可以使用到优先级队列)
  2. 初始化并查集:使用并查集数据结构来记录各个顶点的连通性,初始时每个顶点自成一个集合。
  3. 遍历边并检查环路:按权值从小到大的顺序遍历每条边,利用并查集判断这条边连接的两个顶点是否属于不同的集合。如果是,则加入这条边并不会形成环路,因此将其加入到最小生成树中,并将这两个顶点所在的集合合并。
  4. 重复直至完成:重复上述步骤,直到添加了V-1条边(V为图中顶点的数量),此时便形成了包含所有顶点的最小生成树。

        需要注意的是,在应用Kruskal算法时,需要确保图是连通的,因为算法只能处理连通图的最小生成树问题。如果图不是连通的,那么需要先对图进行连通分量的分析,然后对每个连通分量分别求解最小生成树。大致图解如下:

Kruskal算法的实现

        本文的Kruskal算法是在邻接矩阵的基础上进行实现的,邻接矩阵的实现参考上一篇文章,这里先实现边的结构体,给定两个size_t类型表示源地址_srcI以及目标地址_dstI(实际上就是对应顶点的下标),根据模版类型W来存储边的权值_w,并且重载了一个>符,用于后续优先级队列中对于伪函数的使用,实现如下:

		struct Edge
		{
			size_t _srci;
			size_t _dsti;
			W _w;

			Edge(size_t srci, size_t dsti, const W& w)
				:_srci(srci)
				, _dsti(dsti)
				, _w(w)
			{}

			bool operator>(const Edge& e) const
			{
				return _w > e._w;
			}

		};

        需要注意:前面我们将整个邻接矩阵都已经重新命名了,这样做是为了更好的定义最小生成树,毕竟他本质上也是一个图,并且也是在原来的基础上定义的,我们当然可以使用原来的数据结构:

typedef Graph<V, W, MAX_W, Direction> Self;

        接下来,按照上述的实现步骤一步一步实现:(1)初始化,由于最小生成树对于原图可能只是变小于等于原图,其他实际上都是一样的。因此,我们可以根据原图进行初始化,顶点的存储、顶点同下标的映射都是一样的,只是边需要重新构建!其中MAX_W是作为初始化边的值,默认为INT_MAX。(2)使用优先级队列,以升序的方式对上面我们构建的边结构体进行排序,将原图的所有边都放入优先级队列!(3)选出n-1条边,首先定义一个变量size用于储存有多少条边被选,定义一个totalW用于储存权值,定义一个并查集ufs用于查环。每次遍历都会将优先级队列的顶部值取出,上一篇文章中提到过InSet是用于判断是否为同一根节点(判环)的操作,若不为环则按照邻接矩阵的方法构造边,并且也在并查集中合并在一起。(4)这个循环中不论如何都会将优先级队列中的值全部释放,然后退出循环,最后根据size来判断是否可以形成最小生成树并且返回权值。如下为具体的实现:

		W Kruskal(Self& minTree)
		{
			size_t n = _vertexs.size();

			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				minTree._matrix[i].resize(n, MAX_W);
			}

			priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (i < j && _matrix[i][j] != MAX_W)
					{
						minque.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}

			// 选出n-1条边
			int size = 0;
			W totalW = W();
			UnionFindSet ufs(n);
			while (!minque.empty())
			{
				Edge min = minque.top();
				minque.pop();

				if (!ufs.InSet(min._srci, min._dsti))
				{
					cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
					minTree._AddEdge(min._srci, min._dsti, min._w);
					ufs.Union(min._srci, min._dsti);
					++size;
					totalW += min._w;
				}
				else
				{
					cout << "构成环:";
					cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
			}

			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

Prim算法

如何理解Prim算法?

        Prim算法是一种用于求解加权连通无向图中最小生成树的算法。它的核心思想是从一个顶点开始,逐步扩展已选取的顶点集合,直到所有顶点都被包含在内。(使用的就是局部的贪心策略)具体步骤如下:

  1. 选择起始点:从图中任意选择一个顶点作为起始点。
  2. 构建边界集:将起始点加入已选取的顶点集合中,同时维护一个边界顶点集合,这些顶点是已选取顶点集合与未选取顶点集合之间的边界。
  3. 选择轻量级边:在边界集合中选择权值最小的边,将该边以及其连接的未选取顶点加入到已选取集合中。
  4. 更新边界集:更新边界集合,将新加入的顶点作为新的边界顶点。
  5. 重复直至完成:重复步骤3和步骤4,直到所有顶点都被加入到已选取的顶点集合中,此时形成的树即为最小生成树。

        总的来说,Prim算法的关键在于每一步都选择当前最优的选择,即权值最小的边,以此来保证最终得到的是最小生成树。这种贪心策略确保了算法的效率和结果的最优性。大致图解如下:

Prim算法的实现

        由于Prim是由局部逐步扩散到全局的,也就是说他并不会选择到选过的顶点,因此Prim的实现并不需要使用到并查集。对于上面Kruskal提到的Edge以及Self不多阐述。

        由于Prim需要指定一个顶点开始,因此接口相对Kruskal多传了一个顶点。接下来,按照上述的实现步骤一步一步实现:(1)初始化,同Kruskal一样,我们都是使用邻接矩阵来实现的,因此前期初始化是相同的操作,接着,获取对应的顶点下标映射,创建两个bool数组分别用于表示已选取的顶点集合和未选取顶点集合,true表示拥有该顶点,false表示不拥有。最后按照下标映射初始化两个数组,选取的则改为true,未选改为false,完成初始化。(2)使用优先级队列先将开始顶点的边放入队列中,同样设置size和totalW。(3)开始选边,出队列顶的边,通过判断是否在已选取的顶点集合来判断是否可选(可以变相理解为是否成环),如果不在表示为没有选过因此可以选,选取后将已选取的顶点集合和未选取顶点集合分别改变,再根据刚刚选取的点选取他临界的顶点。(4)在这个循环中,可能会出现很多重复的点的情况,但是我们有已选取的顶点集合来判断是否可选,这样不可选的会自动出队列而不被选取,最后根据size来判断是否可以形成最小生成树并且返回权值

        具体实现如下:

		W Prim(Self& minTree, const W& src)
		{
			size_t srci = GetVertexIndex(src);
			size_t n = _vertexs.size();

			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				minTree._matrix[i].resize(n, MAX_W);
			}

			/*set<int> X;
			set<int> Y;
			X.insert(srci);
			for (size_t i = 0; i < n; ++i)
			{
				if (i != srci)
				{
					Y.insert(i);
				}
			}*/

			vector<bool> X(n, false);
			vector<bool> Y(n, true);
			X[srci] = true;
			Y[srci] = false;

			// 从X->Y集合中连接的边里面选出最小的边
			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
			// 先把srci连接的边添加到队列中
			for (size_t i = 0; i < n; ++i)
			{
				if (_matrix[srci][i] != MAX_W)
				{
					minq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}

			cout << "Prim开始选边" << endl;
			size_t size = 0;
			W totalW = W();
			while (!minq.empty())
			{
				Edge min = minq.top();
				minq.pop();

				// 最小边的目标点也在X集合,则构成环
				if (X[min._dsti])
				{
					//cout << "构成环:";
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
				else
				{
					minTree._AddEdge(min._srci, min._dsti, min._w);
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
					X[min._dsti] = true;
					Y[min._dsti] = false;
					++size;
					totalW += min._w;
					if (size == n - 1)
						break;

					for (size_t i = 0; i < n; ++i)
					{
						if (_matrix[min._dsti][i] != MAX_W && Y[i])
						{
							minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
						}
					}
				}
			}

			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

 


                        感谢你耐心的看到这里ღ( ´・ᴗ・` )比心,如有哪里有错误请踢一脚作者o(╥﹏╥)o! 

                                       

                                                                        给个三连再走嘛~  

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

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

相关文章

Linux第79步_使用自旋锁保护某个全局变量来实现“互斥访问”共享资源

自旋锁使用注意事项:自旋锁保护的“临界区”要尽可能的短。 因此&#xff0c;在open()函数中申请“spinlock_t自旋锁结构变量”&#xff0c;然后在release()函数中释放“spinlock_t自旋锁结构变量”&#xff0c;这种方法就行不通了。如果使用一个变量“dev_stats”来表示“共享…

【前端Vue】Vue3+Pinia小兔鲜电商项目第2篇:什么是pinia,1. 创建空Vue项目【附代码文档】

全套笔记资料代码移步&#xff1a; 前往gitee仓库查看 感兴趣的小伙伴可以自取哦&#xff0c;欢迎大家点赞转发~ 全套教程部分目录&#xff1a; 部分文件图片&#xff1a; 什么是pinia Pinia 是 Vue 的专属状态管理库&#xff0c;可以实现跨组件或页面共享状态&#xff0c;是…

javaSwing扫雷

一、介绍 1.1 背景 在1964年 有一个叫“方 块”的游戏&#xff0c;这是扫雷最原始的版本。后来&#xff0c;这个游戏被改成了另一种游戏&#xff0c;叫做“Rlogic”。在这个游戏中&#xff0c;玩家扮演了一名军队的军人&#xff0c;接受了一项艰难的任务&#xff1a;为指挥中…

Linux--gdb调试

一.安装gdb sudo apt install gdb 二.使用gdb 三.gdb的相关操作 gdb 可执行文件名 显示代码: l 加断点: b 行号 启动程序:r(运行之前一定要加断点) 查看断点信息: info break/info b 删除断点信息:delete 断点编号 单步执行:n 打印 :p 显示:display 变量名: 退出:q …

分布式系统的基本特性

一般&#xff0c;分布式系统需要支持以下特性&#xff1a; 资源共享 开放性 并发性 可伸缩性 容错性 透明性 下面分别讨论。 容易理解的 资源共享 一旦授权&#xff0c;可以访问环境中的任何资源。 资源&#xff1a;包括硬件(e.g. printer, scanner, camera)、软件&a…

8.2K star!史上最强Web应用防火墙

&#x1f6a9; 0x01 介绍 长亭雷池SafeLine是长亭科技耗时近 10 年倾情打造的WAF(Web Application Firewall)&#xff0c;一款敢打出口号 “不让黑客越雷池一步” 的 WAF&#xff0c;我愿称之为史上最强的一款Web应用防火墙&#xff0c;足够简单、足够好用、足够强的免费且开源…

详解main函数参数argc、argv及如何传参

目录 1、main()函数参数 2、main函数如何传参 2.1 环境准备 2.2 通过 Powershell 窗口传参 2.3 通过vs界面传参 3、int main() 和 int main(int argc, char *argv[]) 特点 1、main()函数参数 在C语言中&#xff0c;main函数可以带参数。main函数的原型通常为以下两种形式…

Linux本地部署TeslaMate结合内网穿透实现公网访问内网车辆信息

文章目录 1. Docker部署TeslaMate2. 本地访问TeslaMate3. Linux安装Cpolar4. 配置TeslaMate公网地址5. 远程访问TeslaMate6. 固定TeslaMate公网地址7. 固定地址访问TeslaMate TeslaMate是一个开源软件&#xff0c;可以通过连接特斯拉账号&#xff0c;记录行驶历史&#xff0c;统…

【网络原理】HTTP 请求 (Request)详解

文章目录 &#x1f38d;请求格式&#x1f384;认识URL&#x1f338;query string&#x1f338;关于 URL encode &#x1f340;认识 “方法” (method)&#x1f338;GET方法&#x1f338;POST 方法&#x1f338;GET 和 POST 的区别 &#x1f332;认识请求 “报头” (header)&…

揭秘3D大屏制作:轻松上手的必备工具清单!

轻轻松松做出3D可视化大屏&#xff0c;你需要知道这几样东西 3D可视化大屏一、3D可视化大屏介绍二、3D可视化应用领域三、3D可视化的技术四、3D可视化的制作平台五、总结 大家好&#xff0c;这里是程序猿代码之路。在如今信息以及数据爆炸的时代&#xff0c;如何有效地展示和解…

【算法】差分算法详解(模板)

类似于数学中的求导和积分之间的关系&#xff0c;差分可以看成前缀和的逆运算。 差分数组&#xff1a; 首先给定一个原数组a&#xff1a;a[1], a[2], a[3],,,,,, a[n]; 然后我们构造一个数组b &#xff1a; b[1] ,b[2] , b[3],,,,,, b[i]; 使得 a[i] b[1] b[2 ] b[3] ,,,…

Protobuf 的介绍与使用(入门级)

背景 在移动互联网时代&#xff0c;手机流量、电量是最为有限的资源&#xff0c;而移动端的即时通讯应用无疑必须得直面这两点。 解决流量过大的基本方法就是使用高度压缩的通信协议&#xff0c;而数据压缩后流量减小带来的自然结果也就是省电&#xff1a;因为大数据量的传输必…

【随笔】Git -- 解决提交时本地与目标分支不一致导致提交失败(三)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…

Codeforces Round 935 (Div. 3) (A~G)

1945A - Setting up Camp 题意&#xff1a;三种人安排住宿,a只能跟自己住,b只能三个人住,c能1~3个人&#xff0c;问最终最少房间数 思路&#xff1a;a单独安排,b放一起,不足三个人的用c补,然后c按照3人一房间尽可能分配 void solve() {int a , b , c;cin >> a >>…

一番赏小程序开发,潮玩市场创业新选择!

一番赏是目前非常火爆的抽奖模式&#xff0c;拥有不确定性和超高的惊喜感&#xff0c; 各类隐藏款限量款盲盒商品让年轻消费者欲罢不能。在各种流行趋势下&#xff0c;一番上的市场规模逐渐扩大&#xff0c;吸引着无数人入局。 一番赏在市场上主要是以线下商场门店和线上小程…

某招聘系统0day挖掘(获取4站点报告证书)

前言: 21年的挖的漏洞了 漏洞均已提交且均已修复,这里文章只做技术交流 挖掘过程 对我来说,毕竟喜欢直接黑盒挖0day,一个0day挖到后就可以刷上百分。 如该系统正常找了一个招聘系统用的比较多的 如该通用系统,该通用系统存在一个注册功能 正常的进行注册一个账户进去…

Elasticsearch:将 ILM 管理的数据流迁移到数据流生命周期

警告&#xff1a;此功能处于技术预览阶段&#xff0c;可能会在未来版本中更改或删除。 Elastic 将努力解决任何问题&#xff0c;但技术预览版中的功能不受官方 GA 功能的支持 SLA 的约束。目前的最新版本为 8.12。 在本教程中&#xff0c;我们将了解如何将现有数据流&#xff0…

Yolov部署在Windows和Android上

Yolov部署在Windows和Android上 前言主要模块主要流程转换为ONNX 部署代码JAVAC 前言 Yolov是目标检测的利器&#xff0c;工业中运用得很火。尽管网上的Yolov部署资料很多&#xff0c;但是这块内容目前做得还算上成熟。为了将Yolov部署在Android和Windows上费了些功夫&#xff…

‍Java OCR技术全面解析:六大解决方案比较

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

升级你的技能:发现国产操作系统Deepin学习网站的无限可能!

网址&#xff1a;deepin是一款由武汉深之度科技有限公司开发的Linux操作系统。以下是对deepin的详细介绍&#xff1a; 发展历程&#xff1a;deepin最初名为Hiweed Linux&#xff0c;自2004年起开始对外发行。它经历了多次迭代和改进&#xff0c;逐渐发展成为今天广受好评的操作…