最小生成树构建算法 —— Kruskal算法（克鲁斯卡尔算法）、Prim算法（普里姆算法）
目录
1.认识最小生成树
在无向图当中，如果我们从任意一个顶点出发能到达图中的其他所有顶点，这样的图我们叫做连通图；连通图中的所有极大无环子图都是原图的一棵生成树。
极大无环子图中的无环和子图好理解，如何理解这里的极大两个字呢？极大指的是在满足某种特性的前提下（连通性），尽可能多的包含原图的顶点和边。假设原连通图有n个顶点，而极大无环子图要保证连通性，肯定要包含n个顶点，又要保证无环，最多只能包含n-1条边。所以，一个连通图的包含n个顶点，n-1条边的连通子图就是生成树。
如下所示：
可见，连通图的生成树不止一棵，那么什么是最小生成树呢？我们试着给连通图中的每条边带上权值，权值之和最小的生成树就是该连通图的最小生成树（其意义就是用最小的成本让着n个点连通）。
如下所示：
由此可见，该连通图的最小生成树为生成树C。
2.最小生成树构建算法
我们已经知道了什么是最小生成树，那如何构建一棵图的最小生成树呢？连通图的生成树必须包含n个顶点和n-1条边（n是原图的顶点个数），因此构建最小生成树的准则有以下三条：
- 只能使用无向图中的顶点和边来构造最小生成树
- 只能使用恰好n-1条边来连接图中的n个顶点
- 选用的n-1条边不能构成回路
构建最小生成树的经典算法有Kruskal算法（克鲁斯卡尔算法）和Prim算法（普里姆算法），这两个算法都采用了逐步求解的贪心策略。
3.Kruskal算法
Kruskal算法的大致思想：先记录连通图的所有顶点（n个顶点）和所有边，然后每次都从边集中选取权值最小的边以及这条边对应的两个顶点用于组建最小生成树，并且每次添加这条边的时候判断是否会构成环，如果会构成环就舍弃这条边，否则就添加这条边，直到n个顶点都添加进来之后，如果边的条数等于n-1，则构建出来的就是最小生成树。
Kruskal算法流程图：此图源自于《算法导论》
最后的最小生成树如下：权值之和为37。
Kruskal算法流程：任给一个有n个顶点的连通图G{V, E}，其中V是点集，E是边集。
- 首先构造出有n个顶点，不含任何边的图minTree_G{V, NULL}，其中，我们可以把每个顶点单独看成一个集合。
- 然后不断从边集E中取出权值最小的边，如果该边的两个顶点来自不同的集合，则将该边加入到图minTree_G中；如果该边的两个顶点来自同一个集合，在图minTree_G中添加该边就会构成环，需要舍弃。
- 重复第二点，直到所有的点都在同一个集合中。如果此时的添加的边的条数为n-1条，那么构成的图minTree_G就是图G的最小生成树。
Kruskal算法代码示例：示例代码设置为类的成员函数，由于篇幅原因并没有在此给出图这个类的全部代码，文末附完整源代码。
- 需要注意的是：
- 我们每添加一条边的时候，都是选取权值最小的边添加，因此我们可以用一个小根堆存储边的信息。
- 而且，我们添加边的时候，都需要判断是否会构成环，也就是判断这条边的两个顶点是否在同一集合中，因此，我们可以使用并查集这种数据结构来判断是否构成环。不了解并查集这种数据结构的朋友可以看一下这篇文章
- 并查集的原理及实现
https://blog.csdn.net/D5486789_/article/details/144227145 （本文末附并查集源码）
/*
* V: 顶点的类型
* W: 权值的类型
* MAX_VAL: 权值的最大值，表示两个顶点之间没有关系，默认是int的最大值
* Direction: 表示该图为有向图还是无向图，默认是无向图
*/
template<class V, class W, W MAX_VAL = INT_MAX, bool Direction = false>
class Graph
{
using Self = Graph<V, W, MAX_VAL, Direction>;
public:
/*定义边这种数据结构，用于表示边*/
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;
}
};
/*
* Kruskal算法
* 接收一个输出型参数，输出当前连通图的生成树
* 返回最小生成树的权值之和
*/
W Kruskal(Self& minTree)
{
// 为这个输出型参数赋初值，用于获取当前连通图的信息
size_t n = _vertexs.size();
minTree._indexMap = _indexMap;
minTree._vertexs = _vertexs;
minTree._matrix.resize(n);
for (int i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n, MAX_VAL);
}
// 构建存储边的小堆，每次选取权值最小的边
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> minque;
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
// 无向图的邻接矩阵是对称的，选取一边即可
if (i < j && _matrix[i][j] != MAX_VAL)
{
minque.push(Edge(i, j, _matrix[i][j]));
}
}
}
// 选出n-1条边
size_t size = 0;
W total_w = W();
UnionFindSet ufs(n);
while (!minque.empty())
{
// 选取权值最小的边
Edge min_edge = minque.top();
minque.pop();
// 判断如果选取这条边是否构成环
if (!ufs.InSet(min_edge._srci, min_edge._dsti))
{
// 这条边的两个顶点不在一个集合中，可以选取这条边，不会形成环
// 添加这条边到最小生成树中
minTree.AddEdge(min_edge._srci, min_edge._dsti, min_edge._w);
// 将这条边的两个顶点加入到同一个集合
ufs.Union(min_edge._srci, min_edge._dsti);
// 更新选取的变数和权值和
++size;
total_w += min_edge._w;
}
else
{
// 这条边的两个顶点在一个集合中，不可以选取这条边，会形成环
// 提示构成环并打印构成环的边
std::cout << "构成环: ";
std::cout << _vertexs[min_edge._srci] << "->" << _vertexs[min_edge._dsti] << ":";
std::cout << min_edge._w << std::endl;
}
}
// 存在最小生成树就返回总的权值，否则返回权值类型的默认值
if (size == n - 1)
return total_w;
return W();
}
private:
std::vector<V> _vertexs; // 顶点的集合
std::vector<std::vector<W>> _matrix; // 邻接矩阵
std::map<V, int> _indexMap; // 顶点到下标的映射
};4.Prim算法
Prim算法的大致思想：将图 G{V, E} 中的所有顶点（n个顶点）分成两个集合，分别为集合X和集合Y，集合X初始化为图G中的任意一个顶点，剩余的顶点全部放入集合Y中，每次选取集合X到集合Y中的权值最小的边用于构建最小生成树，直到所有的点都被添加进来之后，如果边的条数为 n-1，则构建出来的就是最小生成树。
- 需要说明一下，Prim算法的实现同样需要借助堆这种数据结构建立小根堆，但是可以不依赖并查集。
- 并且每次选取边的时候，都能够往X集合中添加一个顶点，构建出的图自然而然就是连通的。
Prim算法流程图：此图源自于《算法导论》
最终构建出来的最小生成树如下：权值为37
Prim算法代码示例：
/*
* V: 顶点的类型
* W: 权值的类型
* MAX_VAL: 权值的最大值，表示两个顶点之间没有关系，默认是int的最大值
* Direction: 表示该图为有向图还是无向图，默认是无向图
*/
template<class V, class W, W MAX_VAL = INT_MAX, bool Direction = false>
class Graph
{
using Self = Graph<V, W, MAX_VAL, Direction>;
public:
/*定义边这种数据结构，用于表示边*/
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;
}
};
/*
* Prim算法
* minTree: 这是一个输出型参数，输出当前图的最小生成树
* src: 这是一个起始点，Prim算法从指定的起始点开始构建最小生成树
*/
W Prim(Self& minTree, const V& src)
{
// 输出型参数minTree赋初值
size_t n = _vertexs.size();
minTree._indexMap = _indexMap;
minTree._vertexs = _vertexs;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n, MAX_VAL);
}
// 构建出X集合和Y集合
size_t srci = GetVertexIndex(src); // 获取起始点的编号
std::vector<bool> X(n, false);
std::vector<bool> Y(n, true);
X[srci] = true;
Y[srci] = false;
// 建立一个存储边的小根堆
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> min_heap;
for (int i = 0; i < n; ++i)
{
if (_matrix[srci][i] != MAX_VAL)
{
min_heap.push(Edge(srci, i, _matrix[srci][i]));
}
}
size_t size = 0; // 记录添加的边的条数
W total_w = W(); // 记录总的权值
// 开始找边构建最小生成树
while (!min_heap.empty())
{
Edge min_edge = min_heap.top();
min_heap.pop();
// 判断最小边的目标点是否也在X集合中
if (X[min_edge._dsti] == true)
{
// 选的边的目标点也在集合X中，此时就会出现环，所以，此边不能添加到minTree中
std::cout << "此边构成环，应舍弃，舍弃的边为 -> ";
std::cout << "(" << min_edge._srci << "," << min_edge._dsti << ")";
std::cout << ":" << min_edge._w << std::endl;
}
else
{
// 选的边的目标点不在集合中，不会出现环，将此边添加到minTree中
minTree.AddEdge(min_edge._srci, min_edge._dsti, min_edge._w);
// 修该集合中边的从属关系
X[min_edge._dsti] = true;
Y[min_edge._dsti] = false;
// 更新需要记录的值
++size;
total_w += min_edge._w;
// 如果已经添加了n-1条边，说明已经生成了最小生成树，直接结束循环即可
if (size == n - 1)
{
break;
}
// 添加该边的目标点所连接的且没有添加过的边
for (size_t i = 0; i < n; ++i)
{
// 没有添加过的点在Y集合中
if (_matrix[min_edge._dsti][i] != MAX_VAL && Y[i] == true)
{
min_heap.push(Edge(min_edge._dsti, i, _matrix[min_edge._dsti][i]));
}
}
}
}
if (size == n - 1)
{
return total_w;
}
else
{
return W();
}
}
private:
std::vector<V> _vertexs; // 顶点的集合
std::vector<std::vector<W>> _matrix; // 邻接矩阵
std::map<V, int> _indexMap; // 顶点到下标的映射
};5.源码附录
最小生成树算法源码（Graph.h）
#include <vector>
#include <map>
#include <queue> // For std::priority_queue
#include <algorithm> // For std::greater
#include <stdexcept> // For std::invalid_argument
#include "UnionFindSet.h" // For class UnionFindSet
namespace Link_Matrix // 邻接矩阵存储的图
{
/*
* V: 顶点的类型
* W: 权值的类型
* MAX_VAL: 权值的最大值，表示两个顶点之间没有关系，默认是int的最大值
* Direction: 表示该图为有向图还是无向图，默认是无向图
*/
template<class V, class W, W MAX_VAL = INT_MAX, bool Direction = false>
class Graph
{
using Self = Graph<V, W, MAX_VAL, Direction>;
public:
/*********************************图的基础操作***********************************/
// 默认构造函数
Graph() = default;
// 构造函数
Graph(const V* arr, size_t n)
{
// 把所有的顶点存储起来，并将顶点和顶点的下标建立映射关系，相当于为顶点编号
_vertexs.reserve(n);
for (int i = 0; i < n; ++i)
{
_vertexs.push_back(arr[i]);
_indexMap[arr[i]] = i;
}
// 为邻接矩阵开辟空间，并全部初始化为MAX_VAL，用于后续手动添加边
_matrix.resize(n);
for (int i = 0; i < _matrix.size(); ++i)
{
_matrix[i].resize(n, MAX_VAL);
}
}
// 获取顶点的索引
size_t GetVertexIndex(const V& vertex)
{
auto it = _indexMap.find(vertex);
if (it != _indexMap.end()) // 找到了对应的顶点
{
return it->second;
}
else // 该顶点不存在
{
throw invalid_argument("顶点不存在");
return -1;
}
}
// 根据点添加边
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 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)
{
//cout << 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_VAL)
{
printf("%4c", '*');
}
else
{
printf("%4d", _matrix[i][j]);
}
}
cout << endl;
}
cout << endl;
}
/**********************************图的最小生成树********************************/
/*定义边这种数据结构，用于表示边*/
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;
}
};
/*
* Kruskal算法
* 接收一个输出型参数，输出当前连通图的生成树
* 返回最小生成树的权值之和
*/
W Kruskal(Self& minTree)
{
// 为这个输出型参数赋初值，用于获取当前连通图的信息
size_t n = _vertexs.size();
minTree._indexMap = _indexMap;
minTree._vertexs = _vertexs;
minTree._matrix.resize(n);
for (int i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n, MAX_VAL);
}
// 构建存储边的小堆，每次选取权值最小的边
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> minque;
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
// 无向图的邻接矩阵是对称的，选取一边即可
if (i < j && _matrix[i][j] != MAX_VAL)
{
minque.push(Edge(i, j, _matrix[i][j]));
}
}
}
// 选出n-1条边
size_t size = 0;
W total_w = W();
// 使用并查集来表示集合
UnionFindSet ufs(n);
// 开始选边
while (!minque.empty())
{
// 选取权值最小的边
Edge min_edge = minque.top();
minque.pop();
// 判断如果选取这条边是否构成环
if (!ufs.InSet(min_edge._srci, min_edge._dsti))
{
// 这条边的两个顶点不在一个集合中，可以选取这条边，不会形成环
// 添加这条边到最小生成树中
minTree.AddEdge(min_edge._srci, min_edge._dsti, min_edge._w);
// 将这条边的两个顶点加入到同一个集合
ufs.Union(min_edge._srci, min_edge._dsti);
// 更新选取的变数和权值和
++size;
total_w += min_edge._w;
}
else
{
// 这条边的两个顶点在一个集合中，不可以选取这条边，会形成环
// 提示构成环并打印构成环的边
std::cout << "构成环: ";
std::cout << _vertexs[min_edge._srci] << "->" << _vertexs[min_edge._dsti] << ":";
std::cout << min_edge._w << std::endl;
}
}
// 存在最小生成树就返回总的权值，否则返回权值类型的默认值
if (size == n - 1)
return total_w;
return W();
}
/*
* Prim算法
* minTree: 这是一个输出型参数，输出当前图的最小生成树
* src: 这是一个起始点，Prim算法从指定的起始点开始构建最小生成树
*/
W Prim(Self& minTree, const V& src)
{
// 输出型参数minTree赋初值
size_t n = _vertexs.size();
minTree._indexMap = _indexMap;
minTree._vertexs = _vertexs;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n,MAX_VAL);
}
// 构建出X集合和Y集合
size_t srci = GetVertexIndex(src); // 获取起始点的编号
std::vector<bool> X(n, false);
std::vector<bool> Y(n, true);
X[srci] = true;
Y[srci] = false;
// 建立一个存储边的小根堆
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> min_heap;
for (int i = 0; i < n; ++i)
{
if (_matrix[srci][i] != MAX_VAL)
{
min_heap.push(Edge(srci, i, _matrix[srci][i]));
}
}
size_t size = 0; // 记录添加的边的条数
W total_w = W(); // 记录总的权值
// 开始找边构建最小生成树
while (!min_heap.empty())
{
Edge min_edge = min_heap.top();
min_heap.pop();
// 判断最小边的目标点是否也在X集合中
if (X[min_edge._dsti] == true)
{
// 选的边的目标点也在集合X中，此时就会出现环，所以，此边不能添加到minTree中
std::cout << "此边构成环，应舍弃，舍弃的边为 -> ";
std::cout << "(" << min_edge._srci << "," << min_edge._dsti << ")";
std::cout << ":" << min_edge._w << std::endl;
}
else
{
// 选的边的目标点不在集合中，不会出现环，将此边添加到minTree中
minTree.AddEdge(min_edge._srci, min_edge._dsti, min_edge._w);
// 修该集合中边的从属关系
X[min_edge._dsti] = true;
Y[min_edge._dsti] = false;
// 更新需要记录的值
++size;
total_w += min_edge._w;
// 如果已经添加了n-1条边，说明已经生成了最小生成树，直接结束循环即可
if (size == n - 1)
{
break;
}
// 添加该边的目标点所连接的且没有添加过的边
for (size_t i = 0; i < n; ++i)
{
// 没有添加过的点在Y集合中
if (_matrix[min_edge._dsti][i] != MAX_VAL && Y[i] == true)
{
min_heap.push(Edge(min_edge._dsti, i, _matrix[min_edge._dsti][i]));
}
}
}
}
if (size == n - 1)
{
return total_w;
}
else
{
return W();
}
}
private:
std::vector<V> _vertexs; // 顶点的集合
std::vector<std::vector<W>> _matrix; // 邻接矩阵
std::map<V, int> _indexMap; // 顶点到下标的映射
};
}并查集源码（UnionFindSet.h）
#include <iostream>
#include <vector>
#include <map>
class UnionFindSet
{
public:
// 构造函数
UnionFindSet(size_t n)
:_ufs(n, -1)
{}
// 合并两个元素所在的集合
void Union(int x1, int x2)
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
// 如果本身就在一个集合就没必要合并了
if (root1 == root2)
return;
// 控制数据量小的往大的集合合并
if (abs(_ufs[root1]) < abs(_ufs[root2]))
std::swap(root1, root2);
_ufs[root1] += _ufs[root2];
_ufs[root2] = root1;
}
// 查找一个元素所在的集合
int FindRoot(int x)
{
int root = x;
while (_ufs[root] >= 0)
{
root = _ufs[root];
}
// 路径压缩
while (_ufs[x] >= 0)
{
int parent = _ufs[x];
_ufs[x] = root;
x = parent;
}
return root;
}
// 判断两个元素是否在同一个集合
bool InSet(int x1, int x2)
{
return FindRoot(x1) == FindRoot(x2);
}
// 获取并查集中集合的个数
size_t SetSize()
{
size_t size = 0;
for (size_t i = 0; i < _ufs.size(); ++i)
{
if (_ufs[i] < 0)
{
++size;
}
}
return size;
}
private:
std::vector<int> _ufs; // 用vector充当并查集的底层结构
};原文地址：https://blog.csdn.net/D5486789_/article/details/144293337
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！