【c++高阶DS】最小生成树

Alt

🔥个人主页：Quitecoder

🔥专栏：c++笔记仓

Alt

目录

  • 01.最小生成树
    • Kruskal算法
    • Prim算法

01.最小生成树

连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不在连通；反之，在其中引入任何一条新边，都会形成一条回路，且这些边的权值之和最小

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

  1. 只能使用图中的边来构造最小生成树
  2. 只能使用恰好n-1条边来连接图中的n个顶点
  3. 选用的n-1条边不能构成回路

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

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

Kruskal算法

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

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

  • 其次不断从E中取出权值最小的一条边(若有多条任取其一)，若该边的两个顶点来自不同的连通分量，则将此边加入到G中。如此重复，直到所有顶点在同一个连通分量上为止。

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

在这里插入图片描述

一个加权无向图：由顶点集 V V V 和边集 E E E 组成，边以 ( u , v , w ) (u, v, w) (u,v,w) 的形式表示，表示从 u u u 到 v v v 的边权重为 w w w。

输出
最小生成树的边集，以及最小生成树的总权值。

具体步骤

  1. 排序边集
    将边集按照权值 w w w 从小到大排序。

  2. 初始化

    • 使用并查集（Union-Find）来检测环路。
    • 初始化每个顶点为一个单独的集合。

  3. 遍历边集
    按权值从小到大遍历每条边 ( u , v , w ) (u, v, w) (u,v,w)：

    • 如果 u u u 和 v v v 不在同一个集合中（不形成环），将该边加入最小生成树，并合并 u u u 和 v v v 所在的集合。
    • 如果 u u u 和 v v v 已经在同一集合中，跳过该边。

  4. 终止条件
    当最小生成树包含 n − 1 n-1 n−1 条边时，停止。

typedef Graph<V, W, MAX_W, Direction> Self;
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 this->_w > e._w;
	}
};
W Kruskal(Self& minTree)
{
     minTree._vertexs = _vertexs;
     minTree._indexMap = _indexMap;
     minTree._matrix.resize(_vertexs.size());
	 for (auto& e : minTree._matrix)
	 {
		 e.resize(_vertexs.size(), MAX_W);
	 }
	 priority_queue<Edge,vector<Edge>,greater<Edge>> minq;
	for (int i = 0; i < _vertexs.size();i++)
	{
		for (int j = 0; j < _vertexs.size(); j++)
		{
			if (i<j && _matrix[i][j] != MAX_W)
			{
				minq.push(Edge(i, j, _matrix[i][j]));
			}
		}
	}
	int SIZE = 0;
	W totalW = W();
	UnionFindSet ufs(_vertexs.size());
	while (!minq.empty())
	{
		Edge min = minq.top();
		minq.pop();
		if (!ufs.InSet(min._srci, min._dsti))
		{
			minTree._AddEdge(min._srci, min._dsti, min._w);
			ufs.Union(min._srci, min._dsti);
			++SIZE;
			totalW += min._w;
		}
	}
	if (SIZE == _vertexs.size()-1)
		return totalW;

	else return W();
}

功能概述

  1. 数据结构定义：

    • Edge 结构体：表示一条边，包含三个成员：起点 srci，终点 dsti，以及边的权重 _w。
    • operator>：重载了比较运算符 >，用于在优先队列中进行边的排序，确保每次从队列中取出的边是当前最小的权重边

  2. Kruskal算法的实现：

    • 初始化优先队列（minq）：
      使用最小堆（priority_queue<Edge, vector<Edge>, greater<Edge>>）存储所有的边，边根据其权重进行排序，确保每次从队列中提取的是权重最小的边。

    • 遍历图的边：
      通过两重循环遍历图的邻接矩阵 _matrix，将所有权值不等于 MAX_W（即没有边的情况下）且符合 i < j 条件的边加入优先队列。此处 i < j 是为了确保只加入上三角部分的边，从而避免重复加入相同的无向边（因为无向图的边会对称）。

    • 并查集（Union-Find）：
      初始化并查集 ufs，并使用 InSet 和 Union 方法检查边是否可以加入最小生成树：

      • InSet(min._srci, min._dsti)：检查 srci 和 dsti 是否已经在同一集合中，若是，则说明加入这条边会形成环，不应该加入。
      • Union(min._srci, min._dsti)：若这条边不形成环，则将这条边加入生成树，并将两个顶点所在的集合合并。

    • 累积最小生成树的权重：
      每加入一条边，就将它的权重加到 totalW 上，同时增加 SIZE（记录当前生成树中的边数）。

    • 判断最小生成树是否构建完成：
      生成树完成的条件是边数 SIZE 等于 顶点数 - 1。若是，则返回最小生成树的总权重 totalW。如果图不连通，无法生成一个完整的生成树，则返回默认的 W()（一个无效或空的结果）。

代码的关键点

  1. 优先队列的使用：

    • 使用 priority_queue（最小堆）存储边，确保总是能从队列中取出权值最小的边，这保证了 Kruskal 算法中贪心策略的有效性。即每次选择当前最小的边加入生成树。

  2. 并查集（Union-Find）：

    • UnionFindSet 类是并查集的实现，它支持 InSet（检查两个元素是否属于同一集合）和 Union（合并两个集合）操作，采用路径压缩和按秩合并来提高效率。

  3. 判断图是否连通：

    • 如果 SIZE == _vertexs.size() - 1，说明生成树构建完成，返回总权重。否则，返回 W()，表示图不连通，无法生成最小生成树。

这里我们增加边传的是下标而不是顶点，我们对原来的函数进行修改，仅调用它的子函数即可

void AddEdge(const V& src, const V& dst, const W& w)
{
	size_t srci = GetVertexIndex(src);
	size_t dsti = GetVertexIndex(dst);
	_matrix[srci][dsti] = w;
	if (Direction == false)
	{
		_matrix[dsti][srci] = w;
	}
}

改版：

void _AddEdge(size_t srci, size_t dsti, const W& w)
{
	_matrix[srci][dsti] = w;
	if (Direction == false)
	{
		_matrix[dsti][srci] = w;
	}
}
void AddEdge(const V& src, const V& dst, const W& w)
{
	size_t srci = GetVertexIndex(src);
	size_t dsti = GetVertexIndex(dst);
	_AddEdge(srci, dsti, w);
}

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(_vertexs.size());
	for (auto& e : minTree._matrix)
	{
		e.resize(_vertexs.size(), MAX_W);
	}

	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[min._dsti][i]));
		}
	}
	size_t SIZE = 0;
	W totalW = W();
	while (!minq.empty())
	{
		Edge min = minq.top();
		minq.pop();

		if (X[min._dsti] == true)
		{
			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 && X[i] == false)
				{
					minq.push(Edge(min._dsti, i, _matrix[srci][i]));
				}
			}
		}
	}
	if (SIZE == n - 1)
		return totalW;

	else return W();
}

测试：

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('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);
	Graph<char, int> kminTree; // 初始化与原图相同的顶点集合
	cout << "Prim:" << g.Prim(kminTree,'a') << endl;
	kminTree.Print();
	
}

在这里插入图片描述

以下是代码逻辑的详细分解：

1. 输入与初始化

输入参数

  • minTree: 用于存储最小生成树的图（结果）。
  • src: 起始顶点（用于选择生成树的起点）。

初始化

size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();

minTree._vertexs = _vertexs;
minTree._indexMap = _indexMap;
minTree._matrix.resize(_vertexs.size());
for (auto& e : minTree._matrix)
{
    e.resize(_vertexs.size(), MAX_W);
}
  • 获取起点的索引 srci。
  • 将原图的顶点集合和顶点索引映射复制到 minTree 中，初始化 minTree 的邻接矩阵，初始权值为 MAX_W（无边）。
  • 创建辅助集合 X，用于表示已加入生成树的顶点：
    vector<bool> X(n, false);
X[srci] = true;
    其中，X[srci] = true 表示起点已加入生成树。

2. 优先队列初始化

priority_queue<Edge, vector<Edge>, greater<Edge>> minq;

for (size_t i = 0; i < n; i++)
{
    if (_matrix[srci][i] != MAX_W)
    {
        minq.push(Edge(srci, i, _matrix[srci][i]));
    }
}
  • 创建一个最小堆（priority_queue），用来存储当前生成树与其他顶点之间的边，并按照权值从小到大排序。
  • 将起始顶点 srci 与所有邻接顶点的边加入队列。
  • 这样，队列中会保存以 srci 为起点的所有候选边，边按照权值排序。

3. 循环扩展生成树

size_t SIZE = 0;
W totalW = W();
while (!minq.empty())
{
    Edge min = minq.top();
    minq.pop();
  • SIZE 用于记录生成树中已加入的边的数量。
  • totalW 用于记录生成树的总权值。
  • 从优先队列中取出权值最小的边 min，这一步保证了每次选择的边是当前可行边中权值最小的（贪心策略）。

3.1 判断目标顶点是否已加入生成树

if (X[min._dsti] == true)
    continue;
  • 如果边的目标顶点 min._dsti 已在生成树中，则跳过（避免构成环）。

3.2 加入生成树

minTree._AddEdge(min._srci, min._dsti, min._w);
cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;

X[min._dsti] = true;
++SIZE;
totalW += min._w;
if (SIZE == n - 1) break;
  • 将边 min 加入生成树（minTree），并打印出该边的起点、终点和权值。
  • 将目标顶点 min._dsti 标记为已加入生成树，并更新总权值 totalW 和边计数 SIZE。
  • 如果边数达到 n-1（最小生成树的边数），提前结束循环。

3.3 更新优先队列

for (size_t i = 0; i < n; i++)
{
    if (_matrix[min._dsti][i] != MAX_W && X[i] == false)
    {
        minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
    }
}
  • 遍历目标顶点 min._dsti 的所有邻接顶点。
  • 如果存在一条边，且目标顶点未加入生成树，则将这条边加入优先队列。
  • 通过这一步，优先队列总是包含当前生成树 X 和未加入生成树的顶点 Y 之间的所有候选边。

4. 检查生成树状态并返回结果

if (SIZE == n - 1)
    return totalW;
else
    return W();
  • 如果边数 SIZE == n-1，说明最小生成树构建完成，返回总权值 totalW。
  • 如果图不连通，无法生成完整的最小生成树，返回默认的 W()（表示无效结果）。

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

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

相关文章

自学记录鸿蒙API 13：实现人脸比对Core Vision Face Comparator

自学记录鸿蒙API 13：实现人脸比对Core Vision Face Comparator

完成了文本识别和人脸检测的项目后&#xff0c;我发现人脸比对是一个更有趣的一个小技术玩意儿。我决定整一整&#xff0c;也就是对HarmonyOS Next最新版本API 13中的Core Vision Face Comparator API的学习&#xff0c;这项技术能够对人脸进行高精度比对&#xff0c;并给出相似…
阅读更多...
2024/12/29 黄冈师范学院计算机学院网络工程《路由期末复习作业一》

2024/12/29 黄冈师范学院计算机学院网络工程《路由期末复习作业一》

一、选择题 1.某公司为其一些远程小站点预留了网段 172.29.100.0/26&#xff0c;每一个站点有10个IP设备接到网络&#xff0c;下面那个VLSM掩码能够为该需求提供最小数量的主机数目 &#xff08; &#xff09; A./27 B./28 C./29 D./30 -首先审题我们需要搞清楚站点与网…
阅读更多...
redis cluster集群

redis cluster集群

华子目录 什么是redis集群redis cluster的体系架构什么是数据sharding&#xff1f;什么是hash tag集群中删除或新增节点&#xff0c;数据如何迁移&#xff1f;redis集群如何使用gossip通信?定义meet信息ping消息pong消息fail消息&#xff08;不是用gossip协议实现的&#xff0…
阅读更多...
PrimeVue菜单模块（Menu），看api的重要性

PrimeVue菜单模块（Menu），看api的重要性

以下是对PrimeVue菜单模块&#xff08;Menu&#xff09;的API属性的中文详解&#xff1a; 一、整体概述 PrimeVue的菜单&#xff08;Menu&#xff09;是一个支持动态和静态定位的导航/命令组件&#xff0c;其API通过定义一些辅助的属性&#xff08;props&#xff09;、事件等&…
阅读更多...
STM32中断详解

STM32中断详解

STM32中断详解 NVIC 中断系统中断向量表相关寄存器中断优先级中断配置 外部中断实验EXTI框图外部中断/事件线映射中断步骤初始化代码实现 定时器中断通用定时器相关功能标号1&#xff1a;时钟源标号 2&#xff1a;控制器标号 3&#xff1a;时基单元 代码实现 NVIC 中断系统 STM…
阅读更多...
从零开始开发纯血鸿蒙应用之逻辑封装

从零开始开发纯血鸿蒙应用之逻辑封装

从零开始开发纯血鸿蒙应用 一、前言二、逻辑封装的原则三、实现 FileUtil1、统一的存放位置2、文件的增删改查2.1、文件创建与文件保存2.2、文件读取2.2.1、读取内部文件2.2.2、读取外部文件 3、文件删除 四、总结 一、前言 应用的动态&#xff0c;借助 UI 响应完成&#xff0…
阅读更多...
《机器学习》——线性回归模型

《机器学习》——线性回归模型

文章目录 线性回归模型简介一元线性回归模型多元线性回归模型误差项分析一元线性模型实例完整代码 多元线性模型实例完整代码 线性回归模型简介 线性回归是利用数理统计中回归分析&#xff0c;来确定两种或两种以上变量间相互依赖的定量关系的一种统计分析方法。 相关关系&…
阅读更多...
【深度学习环境】NVIDIA Driver、Cuda和Pytorch（centos9机器，要用到显示器）

【深度学习环境】NVIDIA Driver、Cuda和Pytorch（centos9机器，要用到显示器）

文章目录 一 、Anaconda install二、 NIVIDIA driver install三、 Cuda install四、Pytorch install 一 、Anaconda install Step 1 Go to the official website: https://www.anaconda.com/download Input your email and submit. Step 2 Select your version, and click i…
阅读更多...
在HTML中使用Vue如何使用嵌套循环把集合中的对象集合中的对象元素取出来（我的意思是集合中还有一个集合那种）

在HTML中使用Vue如何使用嵌套循环把集合中的对象集合中的对象元素取出来（我的意思是集合中还有一个集合那种）

在 Vue.js 中处理嵌套集合&#xff08;即集合中的对象包含另一个集合&#xff09;时&#xff0c;使用多重 v-for 指令来遍历这些层次结构。每个 v-for 指令可以用于迭代一个特定级别的数据集&#xff0c;并且可以在模板中嵌套多个 v-for 来访问更深层次的数据。 例如&#xff…
阅读更多...
ip归属地是什么意思？ip归属地是实时定位吗

ip归属地是什么意思？ip归属地是实时定位吗

在数字化时代&#xff0c;IP地址作为网络设备的唯一标识符&#xff0c;不仅关乎设备间的通信&#xff0c;还涉及到用户的网络身份与位置信息。其中&#xff0c;IP归属地作为IP地址的地理位置信息&#xff0c;备受用户关注。本文将详细解析IP归属地的含义&#xff0c;并探讨其是…
阅读更多...
基于BP训练深度学习模型（用于回归）以及验证误差值

基于BP训练深度学习模型（用于回归）以及验证误差值

用原生Python训练了一个BP网络&#xff0c;适合没有pytorch等环境的电脑&#xff0c;并用训练的模型对原始数据进行了预测&#xff0c;拿来估测比较误差值了&#xff0c;可以直接拿去用&#xff08;需根据个人数据来调训练次数、学习效率&#xff09;&#xff0c;代码在文章末。…
阅读更多...
C#冒泡排序

C#冒泡排序

一、冒泡排序基本原理 冒泡排序是一种简单的排序算法。它重复地走访要排序的数列&#xff0c;一次比较两个元素&#xff0c;如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换&#xff0c;也就是说该数列已经排序完成。 以一个简单的整数数…
阅读更多...
折腾日记：如何让吃灰笔记本发挥余热——搭建一个相册服务

折腾日记：如何让吃灰笔记本发挥余热——搭建一个相册服务

背景 之前写过&#xff0c;我在家里用了一台旧的工作站笔记本做了服务器&#xff0c;连上一个绿联的5位硬盘盒实现简单的网盘功能&#xff0c;然而&#xff0c;还是觉的不太理想&#xff0c;比如使用filebrowser虽然可以备份文件和图片&#xff0c;当使用手机使用网页&#xf…
阅读更多...
从0入门自主空中机器人-2-1【无人机硬件框架】

从0入门自主空中机器人-2-1【无人机硬件框架】

关于本课程&#xff1a; 本次课程是一套面向对自主空中机器人感兴趣的学生、爱好者、相关从业人员的免费课程&#xff0c;包含了从硬件组装、机载电脑环境设置、代码部署、实机实验等全套详细流程&#xff0c;带你从0开始&#xff0c;组装属于自己的自主无人机&#xff0c;并让…
阅读更多...
剑指Offer|LCR 013. 二维区域和检索 - 矩阵不可变

剑指Offer|LCR 013. 二维区域和检索 - 矩阵不可变

LCR 013. 二维区域和检索 - 矩阵不可变 给定一个二维矩阵 matrix&#xff0c;以下类型的多个请求&#xff1a; 计算其子矩形范围内元素的总和&#xff0c;该子矩阵的左上角为 (row1, col1) &#xff0c;右下角为 (row2, col2) 。 实现 NumMatrix 类&#xff1a; NumMatrix(…
阅读更多...
接口Mock技术介绍

接口Mock技术介绍

相信学习过程序设计的读者朋友们&#xff0c;一定对“桩&#xff08;Stub&#xff09;”这个概念并不陌生。它是指用来替换一部分功能的程序代码段。桩程序代码段可以用来模拟已有程序的某些功或者是将实现的系统代码的一种临时替代方法。插桩方法被广泛应用于开发和测试工作中…
阅读更多...
深入解析C#异步编程：await 关键字背后的实现原理

深入解析C#异步编程：await 关键字背后的实现原理

在C#中&#xff0c;async 和 await 关键字用于编写异步代码。本文将详细介绍 await 的实现原理&#xff0c;包括状态机的生成、回调函数的注册和触发等关键步骤。 1. 异步方法的基本概念 在C#中&#xff0c;async 关键字标记一个方法为异步方法&#xff0c;而 await 关键字用于…
阅读更多...
【机器学习】SVM支持向量机（一）

【机器学习】SVM支持向量机（一）

介绍 支持向量机&#xff08;Support Vector Machine, SVM&#xff09;是一种监督学习模型&#xff0c;广泛应用于分类和回归分析。SVM 的核心思想是通过找到一个最优的超平面来划分不同类别的数据点&#xff0c;并且尽可能地最大化离该超平面最近的数据点&#xff08;支持向量…
阅读更多...
Unity功能模块一对话系统（1）前置准备

Unity功能模块一对话系统（1）前置准备

也许你也曾被游戏中的对话系统深深吸引&#xff0c;那些精心设计的对白、鲜活的角色配音、甚至是简单的文字对话&#xff0c;往往能让玩家产生强烈的代入感和情感共鸣。如果你正在开发一款游戏&#xff0c;或者计划为你的项目加入一个引人入胜的对话系统&#xff0c;那么 Unity…
阅读更多...
upload-labs关卡记录10

upload-labs关卡记录10

白名单&#xff0c;可以看到已经进行了限制&#xff0c;只能上传这三种后缀的文件&#xff0c;先试一试MIME绕过&#xff1a; 果然不行&#xff1a;观察到是post型&#xff0c;试一试00绕过&#xff1a;没找到路径&#xff0c;绕过失败。 看源码吧&#xff1a; $is_upload f…
阅读更多...
最新文章

Copyright @ 2022~2023