ACM

Kruskal从入门到精通(

求加权连通图的最小生成树的算法。

百度百科

在图论问题中我们有时候会遇到以下问题:在保留尽可能少的边的情况下,使得该图中各点联通,且这些边的边权之和尽可能小。

在保留尽可能少的边的情况下,使得该图中各点联通 ”,其实就是在n个节点的连通图中选择n-1条边。使得这些点构成一棵树,我们称这样的树为图的生成树。

且这些边的边权之和尽可能小”,这样的生成树,我们称之为最小生成树。

ACM竞赛中,最小生成树需要用到kruskal这个算法。这个算法的本质是贪心

本文因作者个人时间限制,不能插图讲解算法原理,因此只介绍该算法怎么做,而不会介绍该算法为什么这么做。以后可能会抽空补齐证明该算法的正确性(咕

简单概括一下Kruskal算法,分为两步骤:

1.存边并排序

用边集数组的形式存储该图,并按照边的权值从小到大排序。

2.贪心增边(利用并查集优化时间复杂度

假定该图为空,从待选的m条边中选取n-1条。从边集数组中按顺序选取,每次选取一条边,就判断该边加入图中是否会成环。如果不成环则选取这条边,否则就舍弃这条边。按照这样的贪心策略选取n-1条之后结束。

这里利用并查集优化时间复杂度,应用在增边与判环这个两个步骤上。并查集介绍可参见我的博文:简单并查集入门

这里把加边抽象为把两个集合合并在一起(两个端点所能连接到的点分别构成两个集合),把判环抽象为判断两个元素是否在同一个集合中( 一条边的两个端点就是两个元素 )。如此一来就巧妙地实现了快速加边与判环。

同时每次增加一条边,我们就把该边的边权加入累加器中。最后的最小生成树的权值就是累加器的值。

下面给出一道例题:HDU1233

我的代码如下:

#include<bits/stdc++.h>
using namespace std;
#define N 101
#define M 5001
struct point{
	int x,y,z;
}e[M];
inline bool cmp(point a,point b){
	return a.z<b.z;
}
int f[N];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
int n,m;
int main(){
	while (scanf("%d",&n)&&n){
		m=n*(n-1)/2;
		for (int i=1;i<=n;i++) f[i]=i;
		for (int i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
		sort(e+1,e+m+1,cmp);
		int sum=0,num=1;
		for (int i=1;i<=m&&num<n;i++){
			int x=find(e[i].x),y=find(e[i].y);
			if (x==y) continue;
			f[x]=y,sum+=e[i].z,num++;
		}
		printf("%d\n",sum);
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注