高阶数据结构学习 —— 图（3）

文章目录

  • 1、最小生成树概念
  • 2、Kruskal算法
  • 3、Prim算法

1、最小生成树概念

先看一下连通图和生成树的概念

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

生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。注意这是无向图中的概念

这一篇来解决最小生成树问题。生成树是通过最少边连通起来所有顶点，其实就是n - 1个边，因为有n个顶点。最小则指所有边的权值和最小。并且这些边不能构成回路。下图就是回路。
在这里插入图片描述

最小生成树通过贪心来设计，有两个算法Kruskal（克鲁斯卡尔）和Prim（普里姆）算法。

2、Kruskal算法

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

每次都选所有边中最小的边，这个可以事先排序一下，更好的办法是优先级队列。至于权值相等的，就是选择其中一个，再去选另一个。但这里因为有不能构成回路问题，无论选哪个边，都需要先判断能否选择。回路的判断就是假设要连ab两点，但在此之前，b已经能通过别的多个边连接到a了，那么此时就不能连接，一连就回路了。所以我们要去走一遍路径看能不能成？这很低效，这里优雅的做法就是用并查集，连接的两点放到一个集合中，这样像上图i和g，当cf连接起来后，ci所在的集合就与gf所在的集合合并起来了，这时候gi就在一个集合中，那么选到gi边时发现在一个集合就不选它了。

最小生成树就是子图，它用到的信息和主图一样。把这个算法函数放在邻接矩阵的Graph类里。

	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Graph<V, W, MAX_W, Direction> Self;
	public:

权值在_matrix这里，这样使用不方便，单独给这个算法造一个边的结构体。

		void _AddEdge(size_t srci, size_t dsti, const W& w)//重载，为了Kruskal算法
		{
			_matrix[srci][dsti] = w;
			if (Direction == false)
				_matrix[dsti][srci] = w;
		}

		void AddEdge(const V& src, const V& dst, const W& w)//增加边的话，应当传源点，目标点，权值
		{
			//即使抛异常程序还能执行，但程序员已经知道程序错误了，最后程序正常地异常结束
			//assert则是暴力退出，且只在debug模式下才有assert，release模式下就屏蔽assert了
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);
			//有向图和无向图区分
			_AddEdge(srci, dsti, w);
		}
		//......
		struct Edge
		{
			size_t _srci;
			size_t _dsti;
			const 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;
			}
		};

		W Kruskal(Self& minTree)
		{
			priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
			size_t n = _vertexs.size();//矩阵大小一定是n阶方阵，也就是n * n
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (i < j && _matrix[i][j] != MAX_W)//为了防止无向图的重复添加，就规定i < j，这样[j][i]就不会插入了
					{
						minque.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}
			//选出n - 1条边
			UnionFindSet ufs(n);
			while (!minque.empty())
			{
				Edge min = minque.top();
				minque.pop();
				if (!ufs.InSameSet(min._srci, min._dsti))
				{
					//通过上面的代码知道，srci和dsti都是顶点的下标，而原AddEdge函数接收的是顶点，所以我们写一个_AddEdge，原函数还可以复用它
					minTree._AddEdge(min._srci, min._dsti, min._w);//不用函数重载的原因是防止V被初始化成size_t类型的
					ufs.Union(min._srci, min._dsti);
				}
			}
		}

现在再添加上权值的记录以及判断。

			//选出n - 1条边
			int sz = 0;
			W totalW = W();
			UnionFindSet ufs(n);
			while (!minque.empty())
			{
				Edge min = minque.top();
				minque.pop();
				if (!ufs.InSet(min._srci, min._dsti))
				{
					//通过上面的代码知道，srci和dsti都是顶点的下标，而原AddEdge函数接收的是顶点，所以我们写一个_AddEdge，原函数还可以复用它
					minTree._AddEdge(min._srci, min._dsti, min._w);//不用函数重载的原因是防止V被初始化成size_t类型的
					ufs.Union(min._srci, min._dsti);
					++sz;
					totalW += min._w;
				}
				else
				{
					cout << "构成回路: " << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
			}
			if (sz == n - 1) return totalW;
			else return W();

如果size是n - 1那就说明能得到最小生成树，然后返回权值和，不能就返回一个缺省值，0。

测试代码。不过类里写上Graph() = default。因为下面的测试是用的无参构造，我们使用默认的就行。

	void TestGraphMinTree()
	{
		const char str[] = "abcdefghi";
		Graph<char, int> g(str, strlen(str));
		g.AddEdge('a', 'b', 4);
		g.AddEdge('a', 'h', 8);
		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);
		Graph<char, int> kminTree;
		cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
		kminTree.Print();
	}

如果这样运行，就会崩掉。原因是传进来的kminTree需要初始化，因为这是默认构造出来的。

			//先初始化成可用的
			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;//#include <functional>
            //矩阵大小一定是n阶方阵，也就是n * n
            //前面有n了，这里就不需要重定义了

3、Prim算法

这个算法在全局选最小。选定一个起点，找连接这个点的最小权值的边，假设选到a连接b的边，那就下一步从b开始找连接b的最小权值的边。

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

Prim的思路就是用两个集合，一个是选中的点，一个是没选中的点，所以它不需要并查集。

	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);
			}
		}

接下来怎么选边？如果用优先级队列，把每一个点连接的边的权值都放进来，这并不可取，因为优先级队列删除的是堆顶，而有的边并不是堆顶，比如上图，到最后时，不能选择ah，但按照优先级队列，有可能就选择上了，这时候a和h应当都在X集合里，所以这个思路是错误的。如果直接遍历选边，其实也不行，效率不高，也有可能出现回路。

这里的思路还是用优先级队列，但做些别的操作，每次添加边时判断是否构成回路，环，判断的方法就是两个点都在一个集合里就会构成回路，不构成的再放进集合里。

		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);
			}
			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 sz = 0;
			W totalW = W();
			while (!minq.empty())
			{
				Edge min = minq.top();
				minq.pop();
				minTree._AddEdge(min._srci, min._dsti, min._w);
				X.insert(min._dsti);
				Y.erase(min._dsti);
				++sz;
				totalW += min._w;
				if (sz == n - 1) break;
				for (size_t i = 0; i < n; ++i)
				{
					if (_matrix[min._dsti][i] != MAX_W && X.count(i) == 0)//i必须不在X里，用计数的函数，为0就说明不在
					{
						minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
					}
				}
			}
			return totalW;
		}

测试代码

		void Print()
		{
			// 顶点
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
			}
			cout << endl;

			// 矩阵
			// 横下标
			cout << "  ";
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				printf("%4d", i);
			}
			cout << endl;

			for (size_t i = 0; i < _matrix.size(); ++i)
			{
				cout << i << " "; // 竖下标
				for (size_t j = 0; j < _matrix[i].size(); ++j)
				{
					if (_matrix[i][j] == MAX_W)
					{
						printf("%4c", '*');
					}
					else
					{
						printf("%4d", _matrix[i][j]);
					}
				}
				cout << endl;
			}
			cout << endl;

			for (size_t i = 0; i < _matrix.size(); ++i)
			{
				for (size_t j = 0; j < _matrix[i].size(); ++j)
				{
					if (i < j && _matrix[i][j] != MAX_W)
					{
						cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
					}
				}
			}

		}

	void TestGraphMinTree()
	{
		const char str[] = "abcdefghi";
		Graph<char, int> g(str, strlen(str));
		g.AddEdge('a', 'b', 4);
		g.AddEdge('a', 'h', 8);
		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);
		Graph<char, int> kminTree;
		cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
		kminTree.Print();
		cout << endl << endl;

		Graph<char, int> pminTree;
		cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
		pminTree.Print();
		cout << endl;
	}

但是按照上面的代码，会构成回路，g和i那里是回路。修改一下

		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);
			}
			vector<bool> X(n, false);
			vector<bool> Y(n, true);
			X[srci] = true;
			Y[srci] = false;
			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 sz = 0;
			W totalW = W();
			while (!minq.empty())
			{
				Edge min = minq.top();
				minq.pop();
				if (X[min._dsti])//起点一定在集合，只要目标点也在就构成环
				{
					cout << "构成环:";
					cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
				else
				{
					minTree._AddEdge(min._srci, min._dsti, min._w);
					X[min._dsti] = true;
					Y[min._dsti] = false;
					++sz;
					totalW += min._w;
					if (sz == n - 1) break;
					for (size_t i = 0; i < n; ++i)
					{
						if (_matrix[min._dsti][i] != MAX_W && Y[i])//i必须在Y集合才能插入
						{
							minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
						}
					}
				}
			} 
			if (sz == n - 1)  return totalW;
			else return W();
		}

K算法是固定的树，P算法起点不同，选出来的树一样，在测试代码最后加上这个来观察。

		for (size_t i = 0; i < strlen(str); ++i)
		{
			cout << "Prim:" << g.Prim(pminTree, str[i]) << endl;
		}

本篇gitee

下一篇写最短路径问题。

结束。

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

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

相关文章

软件产品如何进行跨浏览器测试？

软件产品如何进行跨浏览器测试？

跨浏览器测试是确保Web应用程序的功能在不同浏览器、浏览器版本和操作系统之间保持一致的过程&#xff0c;从而为其用户提供轻松的用户体验。跨浏览器测试涉及浏览器和操作系统的组合&#xff0c;以测试应用程序的响应能力和兼容性。 一、跨浏览器测试的作用 　　1、发现兼容性…
阅读更多...
vite+vue3路由切换滚动条位置重置el-scrollbar

vite+vue3路由切换滚动条位置重置el-scrollbar

vitevue3路由切换滚动条位置重置 本文目录 vitevue3路由切换滚动条位置重置使用原生滚动条使用el-scrollbaruseRoute和useRouter 当切换到新路由时&#xff0c;想要页面滚到顶部&#xff0c;或者是保持原先的滚动位置&#xff0c;就像重新加载页面那样&#xff0c;vue-router 可…
阅读更多...
玻色量子成功研制光量子计算专用光纤恒温控制设备——“量晷”

玻色量子成功研制光量子计算专用光纤恒温控制设备——“量晷”

​近日&#xff0c;北京玻色量子科技有限公司&#xff08;以下简称“玻色量子”&#xff09;成功研制出一款高精度量子计算专用光纤恒温控制设备——“量晷”&#xff0c;该设备能将光纤的温度变化稳定在千分之一摄氏度量级&#xff0c;即能够做到0.001C的温度稳定维持&#xf…
阅读更多...
贪心算法学习------优势洗牌

贪心算法学习------优势洗牌

目录 一&#xff0c;题目 二&#xff0c;题目接口 三&#xff0c;解题思路和代码 全部代码&#xff1a; 一&#xff0c;题目 给定两个数组nums1和nums2,nums1相对于nums2的优势可以用满足nums1[i]>nums2[i]的索引i的数目来描述。 返回nums1的任意排序&#xff0c;使其优…
阅读更多...
视频监控平台EasyCVR分组接口出现“pending”报错，该如何解决？

视频监控平台EasyCVR分组接口出现“pending”报错，该如何解决？

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台可拓展性强、视频能力灵活&#xff0c;能对外分发RTMP、RTSP、…
阅读更多...
高级工技能等级认定---网络设备安全

高级工技能等级认定---网络设备安全

目录 一、DHCP 安全配置 二、SSH配置 三、标准ACL的配置 四、配置交换机端口安全 五、三层交换和ACL的配置 一、DHCP 安全配置 配置要求&#xff1a; 1.给交换机配置enable密码. 2.在交换机上创建VLAN 100&#xff0c;将F0/1-3口改为Access口&#xff0c;并加入到VLAN …
阅读更多...
C++——多态

C++——多态

作者&#xff1a;几冬雪来 时间&#xff1a;2023年10月31日 内容&#xff1a;C部分多态内容讲解 目录 前言&#xff1a; 什么是多态&#xff1a; 虚函数&#xff1a; 协变&#xff1a; c11中override和final&#xff1a; final&#xff1a; override&#xff1a; 重…
阅读更多...
深度学习_2 数据操作

深度学习_2 数据操作

数据操作 机器学习包括的核心组件有&#xff1a; 可以用来学习的数据&#xff08;data&#xff09;&#xff1b;如何转换数据的模型&#xff08;model&#xff09;&#xff1b;一个目标函数&#xff08;objective function&#xff09;&#xff0c;用来量化模型的有效性&…
阅读更多...
HTML5+CSS3+JS小实例：交互式图片鼠标悬停景深对焦效果

HTML5+CSS3+JS小实例：交互式图片鼠标悬停景深对焦效果

实例：交互式图片鼠标悬停景深对焦效果 技术栈：HTML+CSS+JS 效果： 源码： 【HTML】 <!DOCTYPE html> <html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta name="viewport"…
阅读更多...
elasticsearch一些重要的配置参数

elasticsearch一些重要的配置参数

先看一下官网给我们提供的全部的参数配置项 官网地址 官方文档链接&#xff1a;注意版本是8.1Configuring Elasticsearch | Elasticsearch Guide [8.1] | Elastic​编辑https://www.elastic.co/guide/en/elasticsearch/reference/current/settings.html 重要&#xff08;基本…
阅读更多...
SpringBoot+MINIO

SpringBoot+MINIO

Linux安装MINIO https://blog.csdn.net/tongxin_tongmeng/article/details/133934115 MINIO创建桶MINIO创建秘钥MINIO的API路径 http://your-server-ip:9000 注意&#xff1a;API路径在日志文件中/opt/minio/minio.log pom.xml <!-- https://mvnrepository.com/artifact/com…
阅读更多...
最新Microsoft Edge浏览器如何使用圆角

最新Microsoft Edge浏览器如何使用圆角

引入 最近我看了edge官方的文档&#xff0c;里面宣传了edge的最新UI设计&#xff0c;也就是圆角&#xff0c;但是我发现我的浏览器在升级至最新版本之后&#xff0c;却没有圆角 网上有很多人说靠实验性功能即可解锁&#xff0c;但是指令我都试过了&#xff0c;每次都是搜索无结…
阅读更多...
云原生-AWS EC2使用、安全性及国内厂商对比

云原生-AWS EC2使用、安全性及国内厂商对比

目录 什么是EC2启动一个EC2实例连接一个实例控制台ssh Security groups规则默认安全组与自定义安全组 安全性操作系统安全密钥泄漏部署应用安全元数据造成SSRF漏洞出现时敏感信息泄漏网络设置错误 厂商对比参考 本文通过实操&#xff0c;介绍了EC2的基本使用&#xff0c;并在功…
阅读更多...
用起来顺手的在线表结构设计软件工具Itbuilder，与你共享

用起来顺手的在线表结构设计软件工具Itbuilder，与你共享

在线表结构设计软件工具需功能简洁&#xff0c;去除晦涩难懂的设置&#xff0c;化繁为简&#xff0c;实用为上&#xff0c;上手非常容易&#xff0c;这些itbuilder统统可以做到。 itbuilder是一款基于浏览器开发的在线表结构设计软件工具&#xff0c;借助人工智能提高效率&…
阅读更多...
KnowledgeGPT：利用检索和存储访问知识库上增强大型语言模型10.30

KnowledgeGPT：利用检索和存储访问知识库上增强大型语言模型10.30

利用检索和存储访问知识库上增强大型语言模型 摘要引言2 相关研究3方法3.1 任务定义3.2 知识检索3.2.1 代码实现3.2.2 实体链接3.2.3 获取实体信息3.2.4 查找实体或值3.2.5 查找关系 3.3 知识存储 4 实验 摘要 大型语言模型&#xff08;LLM&#xff09;在自然语言处理领域展现…
阅读更多...
Flask_Login使用与源码解读

Flask_Login使用与源码解读

一、前言 用户登录后&#xff0c;验证状态需要记录在会话中&#xff0c;这样浏览不同页面时才能记住这个状态&#xff0c;Flask_Login是Flask的扩展&#xff0c;专门用于管理用户身份验证系统中的验证状态。 注&#xff1a;Flask是一个微框架&#xff0c;仅提供包含基本服务的…
阅读更多...
__attribute__中的constructor和destructor--如何让程序退出时调用指定函数

__attribute__中的constructor和destructor--如何让程序退出时调用指定函数

背景 假设你在开发一个基础组件x&#xff0c;然后你设计了一个x_init接口用来初始化这个组件&#xff0c;相应地你设计了一个x_deinit来去初始化。这样其它模块要用到这个组件时&#xff0c;先调一下x_init, 用完了再调一下x_deinit。init和deinit这是一对很常见的接口&#x…
阅读更多...
前端的简单介绍

前端的简单介绍

前端核心的分析 CSS语法不够强大&#xff0c;比如无法嵌套书写&#xff0c;倒是模块化开发中需要书写很多重复的选择器 没有变量和合理的样式复用机制&#xff0c;使逻辑上相关的属性值必须字面量的心事重复的输出&#xff0c;导致难以维护 CSS预处理器,减少代码的笨重&#…
阅读更多...
网课 - 网页视频-倍速播放-快进-拖动进度条-增大音量 - 火狐Firefox浏览器

网课 - 网页视频-倍速播放-快进-拖动进度条-增大音量 - 火狐Firefox浏览器

本文使用的浏览器为火狐Firefox浏览器。 用浏览器播放视频&#xff0c;比如看网课、看在线电影电视剧时&#xff0c;经常能遇到的情况与解决方案&#xff1a; 音量太小&#xff0c;即使调整到100%还是不够响亮 这时可以安装插件“600% Sound Volume”, 安装之后可在原来音量的…
阅读更多...
测试计划驱动开发模式 TPDD：一种比 TDD 更友好的开发模式

测试计划驱动开发模式 TPDD：一种比 TDD 更友好的开发模式

相信大部分开发团队都在使用TDD&#xff0c;并且还有很多开发团队都 对外声明 在使用 TDD 开发模式。 之所以说是“对外声明”&#xff0c;是因为很多开发团队虽然号称使用的是 TDD 开发模式&#xff0c;实际开发过程中却无法满足 TDD 的要求。 实际上&#xff0c;测试驱动的…
阅读更多...
最新文章

Copyright @ 2022~2023