图论中最小生成树之Kruskal算法
1.背景
Kruskal算法是一种用来寻找最小生成树的算法，基于并查集和贪心算法，由Joseph Kruskal在1956年发表。
用来解决同样问题的还有Prim算法和Boruvka算法等（现在还有一种比较新的算法——solin算法，这个算法的时间复杂度为（nlogm),即在最差的情况下也比Prim算法（nlogn）快，因为（nlogm）几乎达不到）。
三种算法都是贪婪算法的应用，和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。
2.伪代码
int kruskal(int n,int m)
{
/**初始化父节点；
将图的边按权值排序；
每次取权值最小的边；
查：判断每条边的两端点是否属于同一集合，
即是否有相同的根节点；
并：若是同一集合,则舍去，反之合并到同一个根节点下；
将选中的边的权值累加，并保存于变量ans中；
*/
}
3.代码实现
#include<bits/stdc++.h>
#define maxn 1024
using namespace std;
typedef struct Edge
{
int a;
int b;
int w;
}edge;
//定义全局变量，方便
int n,m;
edge a[maxn];
int fa[maxn];//每个点的父节点
int ra[maxn];//?每个点的阶数?
//自建判断函数
int cmp(const void *a,const void *b)
{
return ((edge*)a)->w - ((edge*)b)->w;
}
//初始化树
void init(int n)
{
for(int i = 0;i<n;i++)
{
ra[i] = 0;
fa[i] = i;
}
}
//查找点的父结点
int finde(int x)
{
/*
int root = x;
while(root != fa[root])
{
root = fa[root];
}
while(x != root)
{
int t = fa[x];
fa[x] = root;
x = t;
}
return root;
}
*/
//两种都可以
if(fa[x] == x)
return x;
else
finde(fa[x]);
}
//连结两点
void unite(int x,int y)
{
x = finde(x);
y = finde(y);
if(ra[x] >= ra[y])
{
fa[y] = x;
if(ra[x] == ra[y])
ra[x]++;
}
else
{
fa[x] = y;
}
}
//查找最短路,返回最小值
//n为边，m为点
int kruskal(int n,int m)
{
int nEdge = 0;
int ans = 0;
qsort(a,n,sizeof(a[0]),cmp);
for(int i = 0;i<n && nEdge != m-1;i++)
{
//判断一条边的两个点是否为同一棵树
if(finde(a[i].a) != finde(a[i].b))
{
unite(a[i].a,a[i].b);
ans += a[i].w;
nEdge++;
}
}
//如果跳出循环，即加入的边的数量小于m-1，则表明改无向图不连通，即不存在最小生成数
if(nEdge < m-1)
{
ans = -1;
}
return ans;
}
int main()
{
int Ans;
//n = 0 时退出
while(scanf("%d%d",&n,&m),n)
{
init(m);
for(int i = 0;i<n;i++)
{
scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].w);
}
Ans = kruskal(n,m);
if(Ans == -1)
{
printf("?\n");
}
else
{
printf("%d\n",Ans);
}
}
return 0;
}
运行结果：
kruskal的时间复杂度
- Kruskal算法每次要从都要从剩余的边中选取一个最小的边。通常我们要先对边按权值从小到大排序，这一步的时间复杂度为为O(nlogn)。
- Kruskal算法的实现通常使用并查集，来快速判断两个顶点是否属于同一个集合。最坏的情况可能要枚举完所有的边，此时要循环n次，所以这一步的时间复杂度为O(nα(V))，其中α为Ackermann函数，其增长非常慢，可以视为常数。
- 所以Kruskal算法的时间复杂度为O(nlogn)
大礼包
你渴望力量吗？你渴望变强吗？你渴望原地爆炸吗？
有位老兄为我们准备了图论大礼包!!!
在此感谢大佬@Enstein_Jun！
