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

Crash_Man_CHN · 2025-10-05 23:42:18 · 个人记录

定义

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

性质

1.不唯一

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

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

实现步骤

1. 首先把图按照输入建好然后，初始化并查集fa[i]=i，初始化MST的边集合为空。

2. 将所有边按照权值从小到大进行排序。

3. 遍历每条边，若根节点不同，则将该边加入MSY，并合并，反之若根节点相同（会形成环），则跳过该边。

4. 直到收集到 n-1 条边，说明已经找到，直接break。

5. 若最终收集到 n-1 条边，则构成MST；否则，原图不连通，不存在MST

kruskal模板code

#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;
}