连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不再连通；反之，在其中引入任何一条新边，都会形成一条回路。
若连通图由 n 个顶点组成，则其生成树必含 n 个顶点和 n-1 条边。因此构造最小生成树的准则有三条：
-
只能使用图中的边来构造最小生成树
-
只能使用恰好
n-1条边来连接图中的n个顶点 -
选用的
n-1条边不能构成回路
构造最小生成树的方法：Kruskal 算法和 Prim 算法。这两个算法都采用了逐步求解的贪心策略。
贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的的选择，而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解（也就是说这两种算法并不是万能的）。
🔴 并且最小生成树是不唯一的！
Ⅱ. Kruskal算法
任给一个有 n 个顶点的连通网络 N={V,E}，首先构造一个由这 n 个顶点组成、不含任何边的图 G={V,NULL}，其中每个顶点自成一个连通分量，其次不断从 E 中取出权值最小的一条边 ( 若有多条任取其一 ) ，若该边的两个顶点来自不同的连通分量，则将此边加入到 G 中。
如此重复，直到所有顶点在同一个连通分量上为止。
核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树。
具体实现的时候，由于考虑到每次都要选最小的一条边，那这里就用 优先级队列，也就是一个堆，来进行存放，并且是一个小堆，每次堆顶是最小的边！一般来说我们操作的一般是无向图，所以只需要将矩阵中的上三角行列式中的边入队列即可~
除此之外，还要 判断连接起来的边会不会形成环路，这个时候我们就可以用 并查集 来判断，每次将选择的边对应的邻接顶点加入到并查集中，然后每次新增边的时候 判断一下新增的边引入的邻接顶点是否已经在并查集中，是的话说明形成回路了，则不选这条边~ （🦅 并查集的具体实现翻笔记查找 ）
另外我们还需要单独 弄个结构体包装一下边的属性：
// 为下面一些算法如Kruskal算法做准备的
struct Edge
{
size_t _srci;
size_t _dsti;
W _weight;
Edge(size_t srci, size_t dsti, const W& weight)
:_srci(srci)
, _dsti(dsti)
, _weight(weight)
{}
// 下面要比较边的大小，所以要重载一下比较
bool operator>(const Edge& e) const
{
return _weight > e._weight;
}
}; Kruskal 算法如下所示：
// 下面Kruskal算法接收的参数需要用到默认构造函数
Graph() = default;
typedef Graph<V, W, MAX_W, Direction> Self;
// Kruskal算法
// 下面的minTree是接收的一般是未初始化的图，所以我们要有默认的构造函数
W Kruskal(Self& minTree)
{
// 初始化一下最小生成树的模板
size_t n = _vertexs.size();
minTree._vIndexMap = _vIndexMap;
minTree._vertexs = _vertexs;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
// 默认这些顶点都是不相通的
minTree._matrix[i].resize(n, MAX_W);
}
// 由于我们要从小到大排序，所以得传仿函数过去
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
// 将矩阵中的边入队列
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
// 由于是无向图，我们只需要将上三角行列式中的边加入即可
if (i < j && _matrix[i][j] != MAX_W)
{
pq.push(Edge(i, j, _matrix[i][j]));
}
}
}
// 贪心算法，从最小的边开始选
int size = 0; // 选出n-1条边，所以用size来计数
W sum = W(); // 最后结束的时候返回最小生成树的总权值
UnionFindSet ufs(n); // 并查集
while (!pq.empty())
{
Edge min = pq.top();
pq.pop();
// 判断是否成环
if (!ufs.IsInSameSet(min._srci, min._dsti))
{
cout << minTree._vertexs[min._srci] << "->" <<minTree._vertexs[min._dsti] << ":" << min._weight << endl;
// 将边加上去（注意这里调用的是_AddEdge，接收的参数是下标而不是顶点的版本）
minTree._AddEdge(min._srci, min._dsti, min._weight);
// 再将两个点算入并查集
ufs.Union(min._srci, min._dsti);
sum += min._weight;
++size;
}
else
{
cout << "构成环： ";
cout << minTree._vertexs[min._srci] << "->" <<minTree._vertexs[min._dsti] << ":" << min._weight << endl;
}
}
// 若成功生成最小生成树则返回sum，否则返回默认值
if (size == n - 1)
return sum;
else
return W();
} 我们还要对 AddEdge 函数修改一下，因为我们在 Kruskal 算法中传过去的是下标，但是我们之前的 AddEdge 接收的是顶点，所以我们稍微修改一下~
// 下面函数的子函数，这个接收的参数是下标，这是为了给下面的算法用的
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);
} 下面实现中的测试样例如下图所示：
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 << "Kruskal:" << g.Kruskal(kminTree) << endl;
kminTree.Print();
}
// 运行结果----------------------------------------------------------------------
g->h:1
c->i:2
f->g:2
c->f:4
a->b:4
构成环： g->i:6
构成环： h->i:7
c->d:7
b->c:8
构成环： a->h:9
d->e:9
构成环： e->f:10
构成环： b->h:11
构成环： d->f:14
Kruskal:37
[0]->a
[1]->b
[2]->c
[3]->d
[4]->e
[5]->f
[6]->g
[7]->h
[8]->i
0 1 2 3 4 5 6 7 8
0 * 4 * * * * * * *
1 4 * 8 * * * * * *
2 * 8 * 7 * 4 * * 2
3 * * 7 * 9 * * * *
4 * * * 9 * * * * *
5 * * 4 * * * 2 * *
6 * * * * * 2 * 1 *
7 * * * * * * 1 * *
8 * * 2 * * * * * *Ⅲ. Prim算法
除了 Kruskal 算法以外，普里姆 Prim 算法也是常用的最小生成树算法。虽然在效率上差不多。但是贪心的方式和 Kruskal 完全不同。
prim 算法的核心信仰是：从已知顶点集合，扩散寻找最短距离的边。它的实现方式和 Dijkstra算法相似但稍微有所区别，Dijkstra 是求单源最短路径。而每计算一个点需要对这个点从新更新距离。而 prim 甚至不用更新距离。直接找已知点的邻边最小加入即可！
Prim 算法原理：
- 以某一个点开始，寻找当前该点可以访问的所有的边
- 在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边
- 寻找当前集合可以访问的所有边，重复步骤
2的过程，直到没有新的点可以加入 - 此时由所有边构成的树即为最小生成树
在实现过程中，考虑到每次要挑选已有点的边的最小权值问题，所以我们还是得用优先级队列，效率会比较高一些！但是要注意的是，我们不能一开始就将所有的边入队列，因为 Prim 算法是通过顶点来找边的，只能找已经确认的点的邻接边，所以我们只能边走边将邻接边入队列！
除此之外，我们还需要判断一下加入的边会不会构成环，考虑到 Prim 算法与 Kruskal 算法不同的点也在于 Prim 算法是以顶点为对象的，所以我们时时刻刻都知道哪些点是已经确定的，所以我们可以用一个 vector<bool> vState 来标记这些顶点，true 表示这些顶点在这个集合，false 表示这些顶点不在！
// Prim算法
// minTree是接收的未初始化的图，所以我们要有默认的构造函数
// src是首个顶点
W Prim(Self& minTree, const V& src)
{
size_t srci = GetVertexIndex(src);
// 初始化图，与Kruskal算法一样
size_t n = _vertexs.size();
minTree._vertexs = _vertexs;
minTree._vIndexMap = _vIndexMap;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
minTree._matrix[i].resize(n, MAX_W);
// 使用vector来存储顶点的确认情况：是否在生成树中已经确认（默认是不确认）
// true表示确认存在
// false表示还不确认存在
vector<bool> vState(n, false);
vState[srci] = true; // 注意将首个顶点设置为true
// 初始化优先级队列（与Kruskal算法一样）
// 先将与首个顶点邻接的边入队列
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
for (size_t i = 0; i < n; ++i)
{
if (_matrix[srci][i] != MAX_W)
pq.push(Edge(srci, i, _matrix[srci][i]));
}
size_t size = 0;
W sum = W();
cout << "Prim开始选边" << endl;
while (!pq.empty())
{
Edge min = pq.top();
pq.pop();
// 判断一下是否成环
// 若这条边的目标节点下标是已经确认的，说明是成环的，反之不成环
if (vState[min._dsti] == true)
{
cout << "构成环：";
cout << minTree._vertexs[min._srci] << "->" <<minTree._vertexs[min._dsti] << ":" << min._weight << endl;
}
else
{
cout << minTree._vertexs[min._srci] << "->" <<minTree._vertexs[min._dsti] << ":" << min._weight << endl;
// 将边添加到生成树中去
minTree._AddEdge(min._srci, min._dsti, min._weight);
vState[min._dsti] = true; // 将目的顶点设为确认
sum += min._weight;
size++;
if (size == n - 1)
break;
// 将目的顶点的邻接边入队列，继续循环
for (size_t i = 0; i < n; ++i)
{
// 若它的邻接边是存在的且该目的顶点还未被确认，则入队列
if (_matrix[min._dsti][i] != MAX_W && vState[i] == false)
pq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
}
}
}
// 若成功生成最小生成树则返回sum，否则返回默认值
if (size == n - 1)
return sum;
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> pminTree;
cout << "Prim:" << g.Prim(pminTree, 'a') << endl << endl;
pminTree.Print();
}
// 运行结果
Prim开始选边
a->b:4
a->h:8
h->g:1
g->f:2
f->c:4
c->i:2
构成环：g->i:6
c->d:7
构成环：h->i:7
构成环：b->c:8
d->e:9
Prim:37
[0]->a
[1]->b
[2]->c
[3]->d
[4]->e
[5]->f
[6]->g
[7]->h
[8]->i
0 1 2 3 4 5 6 7 8
0 * 4 * * * * * 8 *
1 4 * * * * * * * *
2 * * * 7 * 4 * * 2
3 * * 7 * 9 * * * *
4 * * * 9 * * * * *
5 * * 4 * * * 2 * *
6 * * * * * 2 * 1 *
7 8 * * * * * 1 * *
8 * * 2 * * * * * *Ⅳ. 两种最小生成树算法的区别
两种算法其实在效率是差不多的，只不过实现的方式是不一样的，具体问题具体分析！
🔴 总的来说，Prim 算法是 以顶点为对象，挑选与点相连的最短边来构成最小生成树。而 Kruskal 算法是以边为对象，不断地加入新的不构成环路的最短边来构成最小生成树。