定义

对于一个图，如果能选出一些边，把所有顶点都连起来，形成一个树状的结构，而且这些边的权重加起来是最小的，那这个树就是最小生成树。

性质

1.不唯一

2.n个点n-1条边，且不是环

3.原来的图的边不在MST中的，添加进去后一定会成环

实现步骤

首先把图按照输入建好然后，初始化并查集fa[i]=i，初始化MST的边集合为空。
将所有边按照权值从小到大进行排序。
遍历每条边，若根节点不同，则将该边加入MSY，并合并，反之若根节点相同（会形成环），则跳过该边。
直到收集到 n-1 条边，说明已经找到，直接break。
若最终收集到 n-1 条边，则构成MST；否则，原图不连通，不存在MST

kruskal模板code

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
struct node
{
	int x,y,w;
}e[N];
bool cmp(node a,node b)
{
	return a.w<b.w;
}
int n,m,fa[N],cnt;
int find(int x)
{
	if(fa[x]==x)return fa[x];
	return fa[x]=find(fa[x]);
}
void unionn(int x,int y)
{
	x=find(x),y=find(y);
	if(x==y)return ;
	fa[x]=y;
	return ;
}
void kruskal()
{
	sort(e+1,e+1+cnt,cmp);
	int sum=0,ans=0;
	for(int i=1;i<=cnt;i++)
	{
		int x=find(e[i].x),y=find(e[i].y);
		if(x==y)continue;
		unionn(e[i].x,e[i].y);
		ans++;
		sum+=e[i].w;
	}
	if(ans<n-1)cout<<"orz";
	else cout<<sum;
	return ;
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		cnt++;
		e[cnt].x=u;
		e[cnt].y=v;
		e[cnt].w=w; 
	}
	kruskal();
	return 0;
}

国庆day2最小生成树总结--上午

文章操作

定义

性质

实现步骤

kruskal模板code

相关推荐

评论

国庆day2最小生成树总结--上午