【图论】kruskal算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了【图论】kruskal算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一.介绍

【图论】kruskal算法,图论,图论,算法

Kruskal（克鲁斯卡尔）算法是一种用于解决最小生成树问题的贪心算法。最小生成树是指在一个连通无向图中，选择一棵包含所有顶点且边权重之和最小的树。

下面是Kruskal算法的基本步骤：

将图中的所有边按照权重从小到大进行排序。
创建一个空的最小生成树集合（并查集实现）。
遍历排序后的边，依次将边加入最小生成树集合中，但要确保加入的边不会形成环路。
- 如果加入边后不会形成环路，则将该边加入最小生成树集合。
- 如果加入边后会形成环路，（即在同一集合）则跳过该边。
重复步骤3，直到最小生成树集合中的边数等于图中顶点数减1，或者遍历完所有边。
最终得到的最小生成树集合即为所求的最小生成树。

Kruskal算法的核心思想是通过不断选择权重最小的边，并判断是否形成环路来构建最小生成树。它不需要事先知道图的连通性，而是通过边的选择来逐步连接图中的顶点，直到所有顶点都被连接为止。

需要注意的是，Kruskal算法适用于解决无向图的最小生成树问题，对于有向图则需要使用其他算法，如Prim算法。此外，Kruskal算法也可以处理带有边权重相同的情况。

二.模板题

P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)文章来源地址https://www.toymoban.com/news/detail-618941.html

三.【AC】代码

#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
inline int read(){
	int ans=0,f=1;
	char cc=getchar();
	while(cc<'0' || cc>'9'){
		if(cc=='-') f=-1;
		cc=getchar();
	}
	while(cc>='0' && cc<='9'){
		ans=(ans<<1)+(ans<<3)+(cc-'0');
		cc=getchar();
	}
	return ans*f;
}
int n,m,ans=0;
bool flag=0;
int fa[5010];
struct Edge{
	int u,v,w;
}edge[maxn];
bool cmp(Edge a,Edge b){
	return a.w<b.w;
}
inline int find(int x){
	return x==fa[x] ? x : fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
	int fx=find(x),fy=find(y);
	fa[fx]=fy;
}
void kruskal(){
	sort(edge+1,edge+m+1,cmp);
	int cnt=0;
	for(int i=1;i<=m;i++){
		int x=edge[i].u,y=edge[i].v;
		if(find(x)==find(y)) continue;
		ans+=edge[i].w;
		merge(x,y);
		cnt++;
		if(cnt==n-1){
			flag=1;
			return;
		} 
	}
}
int main(){
	//读入数据 
	n=read();m=read();
	for(int i=1;i<=m;i++){
		edge[i].u=read();edge[i].v=read();edge[i].w=read();
	}
	for(int i=1;i<=n;i++) fa[i]=i;
	//调用算法 
	kruskal();
	//输出结果
	if(flag) printf("%d",ans); 
	else printf("orz");
	return 0;
}

到了这里，关于【图论】kruskal算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！