在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得
的 w(T) 最小，则此 T 为 G 的最小生成树。
最小生成树其实是最小权重生成树的简称
1、Kruskal算法：
主要步骤：1.对G的边以非降序权重排列；
2.对于排序表中的每条边，如果现在把它放入T不会形成回路的话，则把它加入到生成树T中；否则把它丢弃。
伪代码如下：Kruskal
输入：包含n个顶点的含权连通无向图G=（V，E）
输出：由G生成的最小耗费生成树T组成的边的集合
按非降序权重将E中的边排序
for 每条边 v∈V
MAKESET({v})
end for
T={}
while ∣T∣＜n-1
令（x，y）为E中的下一条边
if FIND(x) ≠ FIND(y) then
将（x，y）加入T
UNION(x，y）
end if
end while
此算法时间复杂度为：Ο(mlogm)
详细代码如下：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1e4 + 5;
int father[maxn];
struct node
{
int u, v, val;
}edge[maxn];
bool cmp(node&a, node&b)
{
return a.val < b.val;
}
int Find(int x)
{
if (x == father[x])
return father[x];
else
return father[x] = Find(father[x]);
}
void join(int x, int y)
{
int fa = Find(x);
int fb = Find(y);
if (fa != fb)
father[fb] = fa;
}
int kruskal(int n, int m)//n个点，m条边的完全连通图的克鲁斯卡尔算法
{
sort(edge, edge + m, cmp);
//初始化并查集
for (int i = 0; i <=n; i++)
father[i] = i;
int ans = 0;
for (int i = 0; i < m; i++)
{
int fa = Find(edge[i].v);
int fb = Find(edge[i].u);
if (fa != fb)
{
join(fa, fb);
ans += edge[i].val;
}
}
return ans;
}
int main()
{
int n;
while (cin >> n && n)
{
int m = (n - 1)*n / 2;
for (int i = 0; i < m; i++)
{
cin >> edge[i].v >> edge[i].u >> edge[i].val;
}
cout << kruskal(n, m) << endl;
}
}
参考：最小生成树——kruskal算法 - YG爱木木 - CSDN博客
2、Prim算法
算法描述：
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
伪代码如下：Prim
输入：包含n个顶点的含权连通无向图G=（V，E）
输出：由G生成的最小耗费生成树T组成的边的集合
T={}; X←{1}; Y←V﹣{1}
for y←2 to n
if y邻接于1 then
N[y]← 1
C[y]← c[1,y]
else
C[y]←∞
end if
end for
for j← 1 to n-1 {寻找n-1条边}
令y∈Y,使得C[y]最小
T←T∪{(y,N[y])} {将边(y,N[y])加入T}
X←X∪{y} {将顶点y加入X}
Y←Y-{y} {从Y删除顶点y}
for 每个邻接于y的顶点w∈Y
if c[y,w]＜C[w] then
N[w]←y
C[w]←c[y,w]
end if
end for
end for
此算法时间复杂度为：Ο(n²)
详细代码如下：
// Prim最小生成树
void Prim(int nStart)
{
int i = 0;
int nIndex=0; // prim最小树的索引，即prims数组的索引
char cPrims[MAX]; // prim最小树的结果数组
int weights[MAX]; // 顶点间边的权值
cPrims[nIndex++] = m_mVexs[nStart].data;
// 初始化"顶点的权值数组"，
// 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
for (i = 0; i < m_nVexNum; i++)
{
weights[i] = GetWeight(nStart, i);
}
for (i = 0; i < m_nVexNum; i ++)
{
if (nStart == i)
{
continue;
}
int min = INF;
int nMinWeightIndex = 0;
for (int k = 0; k < m_nVexNum; k ++)
{
if (weights[k]!= 0 && weights[k] < min)
{
min = weights[k];
nMinWeightIndex = k;
}
}
// 找到下一个最小权重值索引
cPrims[nIndex++] = m_mVexs[nMinWeightIndex].data;
// 以找到的顶点更新其他点到该点的权重值
weights[nMinWeightIndex]=0;
int nNewWeight = 0;
for (int ii = 0; ii < m_nVexNum; ii++)
{
nNewWeight = GetWeight(nMinWeightIndex, ii);
// 该位置需要特别注意
if (0 != weights[ii] && weights[ii] > nNewWeight)
{
weights[ii] = nNewWeight;
}
}
}
// 计算最小生成树的权重值
int nSum = 0;
for (i = 1; i < nIndex; i ++)
{
int min = INF;
int nVexsIndex = GetVIndex(cPrims[i]);
for (int kk = 0; kk < i; kk ++)
{
int nNextVexsIndex = GetVIndex(cPrims[kk]);
int nWeight = GetWeight(nVexsIndex, nNextVexsIndex);
if (nWeight < min)
{
min = nWeight;
}
}
nSum += min;
}
// 打印最小生成树
cout << "PRIM(" << m_mVexs[nStart].data <<")=" << nSum << ": ";
for (i = 0; i < nIndex; i++)
cout << cPrims[i] << " ";
cout << endl;
}
