文章目录
- 引言
- 一、最小生成树的概念
- 二、Kruskal算法
- 2.1 思想
- 2.2 实现
- 三、Prim算法
- 3.1 思想
- 3.2 实现
- 四、Kruskal和Prim的对比
引言
前置知识：【数据结构】并查集
前置知识：【数据结构】图的概念和存储结构
一、最小生成树的概念
最小生成树（Minimum Spanning Tree, MST） 是图论中的一个重要概念，指的是在一个连通的无向图中，选择一部分边，使得这些边连接所有顶点且边权值之和最小，同时生成的子图仍是一个树结构（没有环）。
按照定义，若连通网络由n个顶点组成，则其生成树必含n个顶点，n-1条边。因此，构造最小生成树有3个准则：
- 只能使用该网络的边来构造最小生成树
- 只能使用恰好n-1条边来连接n个顶点
- 选用的这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算法采用全局贪心的策略：
- 每次选取图中权值最小的边。
- 每次选取完后，判断是否构成回路。若构成，则舍弃这条边。
具体图示如下：
2.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();
}
}
细节：
- 输入一个空图，输出最小生成树的总权值，并将空图变为最小生成树。
- count记录已选边数，若达到n-1，则可直接跳出循环，提高效率。
三、Prim算法
3.1 思想
Prim算法采用局部贪心的策略：
- 将已被选择的点看作一个顶点集合，初始状态只有起点在集合中。
- 每次在集合周围查找，找到消耗权值最小即可抵达的点，并将其纳入集合。
具体图示如下：
3.2 实现
思路：
- 采用优先级队列（小堆），将起始点周围的路径存入，以便每次选取集合周围权值最小的边。
- 集合用bool数组表示，每次只有当目标点不在集合中，才将其纳入集合。
- 每次将新点纳入集合后，再将新点周围的路径存入优先级队列，依次迭代。
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();
}
}
细节：
- 输入一个空图和一个起始点，输出最小生成树的总权值，并将空图变为最小生成树。
- count记录已选边数，若达到n-1，则可直接跳出循环，提高效率。
四、Kruskal和Prim的对比
| Kruskal 算法 | Prim 算法 | |
|---|---|---|
| 算法类型 | 贪心算法 | 贪心算法 |
| 适用图类型 | 稀疏图，特别适合边权值分布较广的图 | 稠密图，特别适合顶点多边多的图 |
| 基本思想 | 从边的角度出发，按权值从小到大选择边 | 从顶点出发，每次扩展最小权值的边 |
| 时间复杂度 | O(E log V) | O(E log V) |
| 典型应用 | 网络设计问题，边多且分散的图 | 电网、网络设计问题，稠密的图 |
| 贪心选择标准 | 每次选择权值最小且不形成环的边 | 每次选择最小的连接权值，扩展已加入的顶点集合 |
- Kruskal：适用于稀疏图，因为其从边的角度出发，边的数量相对少时效率更高。
- Prim：适用于稠密图，因为它每次从顶点出发，逐渐扩展树，对于稠密图（边多的图）效率更高
