求最小生成树算一般有两种算法： Prim 和 Kruskal 。 Prim 的时间复杂度为 \(O(|V|^{2})\) ，更适合稠密图。而 Kruskal 的时间复杂度为 \(O(logV)\) 或 \(O(logE)\) 。更适合稀疏图，下面就讲一下 Kruskal 算法的实现。
1.并查集
Kruskal 的核心就是并查集，并查集在 Kruskal 中的作用为 判断两个点是否已经联通。
1.并查集的初始化
并查集是用一个数组储存的，数组下标代表点的序号，而数组下标对应的内容则代表这个点的父亲。在最开始每个点都是独立的，因此每个点的父亲都是自己。
初始化代码：
fa[1005];
...
for(int i = 1;i <= n;i++)
{
fa[i] = i;
}
2.并查集的查找
并查集的查找找的是这个点的最远祖先，代码为：
int find(int x){
if(p[x]==x)
return x;
else
return find(p[x]);
}
但是这种方法效率较慢，下面是一种路径压缩的查找方式。
int find(int x)
{
if(par[x]==x)
return x;
fa[x]=find(fa[x]);
return par[x];
}
也可以写为：
int find(int x)
{
return fa[x]=x?x:fa[x]=find(fa[x]);
}
此时 find(x) 的返回值即为这个点的最远祖先。
3.并查集合并
并查集的名字中有“并”和"查”字，所以并查集的核心就在于合并和查找。
例如，下图为并查集的初始状态。
将 1 和 3合并后的状态：
使用树表示为：
并查集合并的代码为：
void merge(int i,int j){
fa[find(j)] = find(i);
}
2.Kruskal算法
Kruskal 的思想为对每条边的长度进行排序，从短到长一次取边，当这条边所连的点未连接时，将两点进行合并。
图解
例如要求下面这个图的最小生成树的权值。
1.对所有边的长短进行排序：
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | 0 | 4 | 0 | 5 | 0 | 0 |
| 2 | 4 | 0 | 3 | 0 | 0 | 0 |
| 3 | 0 | 3 | 0 | 2 | 6 | 1 |
| 4 | 5 | 0 | 2 | 0 | 9 | 0 |
| 5 | 0 | 0 | 6 | 9 | 0 | 10 |
| 6 | 0 | 0 | 1 | 0 | 10 | 0 |
2.从短到长依次取边，当使用并查集判断两点未连接时，进行合并。
3.最后得到最小生成树如图，权值和为 16 。
例题：拆地毯
代码为：
#include<bits/stdc++.h>
using namespace std;
int find(int x);
int f[100003];
struct edge
{
int u;
int v;
int dis;
}ed[100000];
bool cmp(edge a,edge b)
{
return a.dis>b.dis;
}
int Kruskal(int m,int k)
{
int ans=0;int num = 0;
for(int i = 1;i<=m;i++)
{
int fu=find(ed[i].u);
int fv=find(ed[i].v);
if(fu==fv) continue;
if(fu!=fv)
{
f[fu]=fv;
ans+=ed[i].dis;
num++;
if(num==k) break;
}
}
return ans;
}
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
int main()
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i = 1;i<=n;i++) f[i]=i;
for(int i = 1;i<=m;i++)
{
int x,y,d;
scanf("%d%d%d",&x,&y,&d);
ed[i].u=x; ed[i].v=y; ed[i].dis=d;
}
sort(ed+1,ed+1+m,cmp);
printf("%d",Kruskal(m,k));
return 0;
}