【数据结构】图的最小生成树

快乐的流畅：个人主页

个人专栏：《C游记》《进击的C++》《Linux迷航》

远方有一堆篝火，在为久候之人燃烧！

---

引言

前置知识：【数据结构】并查集
前置知识：【数据结构】图的概念和存储结构

一、最小生成树的概念

最小生成树（Minimum Spanning Tree, MST） 是图论中的一个重要概念，指的是在一个连通的无向图中，选择一部分边，使得这些边连接所有顶点且边权值之和最小，同时生成的子图仍是一个树结构（没有环）。

---

按照定义，若连通网络由n个顶点组成，则其生成树必含n个顶点，n-1条边。因此，构造最小生成树有3个准则：

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

下面讲解两种经典的最小生成树算法——kruskal算法和prim算法，它们都采用了贪心策略来进行实现。

前置声明：

template<class W>
struct Edge
{
int _srci;
int _dsti;
W _w;

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

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

template<class V, class W, W W_MAX = INT_MAX, bool Direction = false>
class Graph
{
typedef Edge<W> Edge;
typedef Graph<V, W, W_MAX, Direction> Self;
//...
}

二、Kruskal算法

2.1 思想

Kruskal算法采用全局贪心的策略：

1. 每次选取图中权值最小的边。
2. 每次选取完后，判断是否构成回路。若构成，则舍弃这条边。

具体图示如下：

2.2 实现

思路：

1. 采用优先级队列（小堆），将所有边存入，以便每次选取全图权值最小的边。
2. 采用并查集，存储已选取的顶点。每次选取边时，判断两侧顶点是否在并查集中，以此判断是否构成回路。

W Kruskal(Self& minTree)
{
minTree._vertexs = _vertexs;
minTree._indexMap = _indexMap;
int n = _edges.size();
minTree._edges.resize(n, vector<W>(n, W_MAX));

priority_queue<Edge, vector<Edge>, greater<Edge>> minHeap;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i < j && _edges[i][j] != W_MAX)//无向图，防止重复记录路径
{
minHeap.push(Edge(i, j, _edges[i][j]));
}
}
}

UnionFindSet<V> ufs(n);
W total = W();
int count = 0;
while (!minHeap.empty())
{
Edge top = minHeap.top();
minHeap.pop();

int srci = top._srci, dsti = top._dsti;
W w = top._w;
if (!ufs.InSet(srci, dsti))
{
minTree._AddEdge(srci, dsti, w);
ufs.Union(srci, dsti);
total += w;
++count;

if (count == n - 1)
{
break;
}

cout << _vertexs[srci] << "--" << _vertexs[dsti] << ":" << w << endl;
}
else
{
cout << _vertexs[srci] << "--" << _vertexs[dsti] << ":" << w << "[构成环]" << endl;
}
}

if (count == n - 1)
{
return total;
}
else
{
return W();
}
}

细节：

1. 输入一个空图，输出最小生成树的总权值，并将空图变为最小生成树。
2. count记录已选边数，若达到n-1，则可直接跳出循环，提高效率。

三、Prim算法

3.1 思想

Prim算法采用局部贪心的策略：

1. 将已被选择的点看作一个顶点集合，初始状态只有起点在集合中。
2. 每次在集合周围查找，找到消耗权值最小即可抵达的点，并将其纳入集合。

具体图示如下：

3.2 实现

思路：

1. 采用优先级队列（小堆），将起始点周围的路径存入，以便每次选取集合周围权值最小的边。
2. 集合用bool数组表示，每次只有当目标点不在集合中，才将其纳入集合。
3. 每次将新点纳入集合后，再将新点周围的路径存入优先级队列，依次迭代。

W Prim(Self& minTree, const V& src)
{
minTree._vertexs = _vertexs;
minTree._indexMap = _indexMap;
int n = _edges.size();
minTree._edges.resize(n, vector<W>(n, W_MAX));

//起始点周围的路径入堆
priority_queue<Edge, vector<Edge>, greater<Edge>> minHeap;
int srci = GetIndex(src);
for (int i = 0; i < n; ++i)
{
if (_edges[srci][i] != W_MAX)
{
minHeap.push(Edge(srci, i, _edges[srci][i]));
}
}

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

W total = W();
int count = 0;
while (!minHeap.empty())
{
Edge top = minHeap.top();
minHeap.pop();

int srci = top._srci, dsti = top._dsti;
W w = top._w;
if (!S[dsti])
{
minTree._AddEdge(srci, dsti, w);
S[dsti] = true;
total += w;
++count;

if (count == n - 1)
{
break;
}

for (int i = 0; i < n; ++i)
{
if (!S[i] && _edges[dsti][i] != W_MAX)//无向图，防止重复记录路径
{
minHeap.push(Edge(dsti, i, _edges[dsti][i]));
}
}

cout << _vertexs[srci] << "--" << _vertexs[dsti] << ":" << w << endl;
}
else
{
cout << _vertexs[srci] << "--" << _vertexs[dsti] << ":" << w << "[构成环]" << endl;
}
}

if (count == n - 1)
{
return total;
}
else
{
return W();
}
}

细节：

1. 输入一个空图和一个起始点，输出最小生成树的总权值，并将空图变为最小生成树。
2. count记录已选边数，若达到n-1，则可直接跳出循环，提高效率。

四、Kruskal和Prim的对比

	Kruskal 算法	Prim 算法
算法类型	贪心算法	贪心算法
适用图类型	稀疏图，特别适合边权值分布较广的图	稠密图，特别适合顶点多边多的图
基本思想	从边的角度出发，按权值从小到大选择边	从顶点出发，每次扩展最小权值的边
时间复杂度	O(E log V)	O(E log V)
典型应用	网络设计问题，边多且分散的图	电网、网络设计问题，稠密的图
贪心选择标准	每次选择权值最小且不形成环的边	每次选择最小的连接权值，扩展已加入的顶点集合

---

• Kruskal：适用于稀疏图，因为其从边的角度出发，边的数量相对少时效率更高。
• Prim：适用于稠密图，因为它每次从顶点出发，逐渐扩展树，对于稠密图（边多的图）效率更高

真诚点赞，手有余香

原文地址：https://blog.csdn.net/2301_79188764/article/details/142172901

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！