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

用户11029103

发布于 2024-12-28 10:38:01

15600

代码可运行

文章被收录于专栏：技术学习技术学习

运行总次数：0

代码可运行

01.最小生成树

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

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

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

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

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

Kruskal算法

任给一个有n个顶点的连通网络N={V,E}，
首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL}，其中每个顶点自成一个连通分量，
其次不断从E中取出权值最小的一条边(若有多条任取其一)，若该边的两个顶点来自不同的连通分量，则将此边加入到G中。如此重复，直到所有顶点在同一个连通分量上为止。
核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树

一个加权无向图：由顶点集

和边集

组成，边以

(u, v, w)

的形式表示，表示从

到

的边权重为

。

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

具体步骤

排序边集 将边集按照权值

从小到大排序。

初始化
- 使用并查集（Union-Find）来检测环路。
- 初始化每个顶点为一个单独的集合。
遍历边集 按权值从小到大遍历每条边

(u, v, w)

：

如果

和

不在同一个集合中（不形成环），将该边加入最小生成树，并合并

和

所在的集合。

如果

和

已经在同一集合中，跳过该边。

终止条件 当最小生成树包含

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

功能概述

数据结构定义：
- Edge 结构体：表示一条边，包含三个成员：起点 srci，终点 dsti，以及边的权重 _w。
- operator>：重载了比较运算符 >，用于在优先队列中进行边的排序，确保每次从队列中取出的边是当前最小的权重边
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()（一个无效或空的结果）。

代码的关键点

优先队列的使用：
- 使用 priority_queue（最小堆）存储边，确保总是能从队列中取出权值最小的边，这保证了 Kruskal 算法中贪心策略的有效性。即每次选择当前最小的边加入生成树。
并查集（Union-Find）：
- UnionFindSet 类是并查集的实现，它支持 InSet（检查两个元素是否属于同一集合）和 Union（合并两个集合）操作，采用路径压缩和按秩合并来提高效率。
判断图是否连通：
- 如果 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()（表示无效结果）。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-12-27，如有侵权请联系 cloudcommunity@tencent.com 删除

排序

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度