最小生成树是什么？

Kruskal算法

转载自a2392008643的博客

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

1. 把图中的所有边按代价从小到大排序；

2. 把图中的n个顶点看成独立的n棵树组成的森林；

3. 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。

4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

代码:(题目:LOJ#123最小生成树)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll f[200005],n,m;
void init(ll m) {for(ll i=1;i<=m;i++) f[i]=i;}
ll getf(ll x) {return f[x]==x?x:f[x]=getf(f[x]);}
bool merge(ll t1,ll t2) {return getf(t1)==getf(t2)?false:(true,f[getf(t2)]=getf(t1));}
struct node{ll x,y,co;}a[500005];
bool cmp(node a,node b) {return a.co<b.co;}
int main()
{
    scanf("%lld %lld",&n,&m);
    for(ll i=1;i<=m;i++) scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].co);
    sort(a+1,a+m+1,cmp);
    init(n);
    ll num=0,cos=0;
    for(ll i=1;i<=m;i++)
    {
        if(merge(a[i].x,a[i].y)) ++num,cos+=a[i].co;
        if(num==n-1) break;
    }
    printf("%lld",cos);
    return 0;
}

Kruskal算法

原文：https://www.cnblogs.com/juruo-zzt/p/11996765.html