最小生成树kruskal算法详解

kruskal算法的思想简单来说就是：每次选择图中最小边权的边，如果边两端的顶点不在相同的连通块中，就把这条边加入到最小生成树中。

具体实现如下：

首先是边的定义，需要判断边的两个端点是否在不同的连通块中，因此边的两个端点的编号一定是需要的：而算法中又涉及边权，因此边权也必须要有。于是可以定义一个结构体，在里面存放边的两个端点编号和边权即可满足需要。

struct edge{
	int u,v;
	int cost;
}E[maxn];

在解决了边的定义后，需要写一个排序函数来让数组E按边权从小到大排序。

bool cmp(edge a,edge b){
	return a.cost<b.cost;
}

kruskal算法实现的代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int maxv=110;
const int maxe=10010;
struct edge{
	int u,v;
	int cost;
}E[maxe];
bool cmp(edge a,edge b){
	return a.cost<b.cost;
}
int father[maxv];
int findFather(int x){
	int a=x;
	while(x!=father[x]){
		x=father[x];
	}
	while(a!=father[a]){
		int z=a;
		a=father[a];
		father[z]=a;
	}
	return x;
}
int kruskal(int n,int m){
	int ans=0,num_edge=0;
	for(int i=0;i<n;i++){
		father[i]=i;
	}
	sort(E,E+m,cmp);
	for(int i=0;i<m;i++){
		int faU=findFather(E[i].u);
		int faV=findFather(E[i].v);
		if(faU!=faV){
			father[faU]=faV;
			ans+=E[i].cost;
			num_edge++;
			if(num_edge==n-1){
				break;
			}
		}
	}
	if(num_edge!=n-1){
		return -1;
	}
	else{
		return ans;
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>E[i].u>>E[i].v>>E[i].cost;
	}
	int ans=kruskal(n,m);
	cout<<ans<<endl;
	return 0;
}

可以发现，kruskal算法的时间复杂度主要来源于对边进行排序，因此其时间复杂度是 $O\left ( ElogE \right )$ ，其中E为图的边数。因此，kruskal算法适合顶点数较多、边数较少的情况。因此如果是稠密图，则用prim算法，如果是稀疏图，则用kruskal算法。