求最小生成树的两种算法

书P363~366
定理：任意一棵最小生成树一定包含无向图中权值最小的边

①Kuskal算法（克鲁斯卡尔）
时间复杂度为O(m log m)

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
struct rec
{
    int x,y,z;
}edge[500010];
int fa[100010],n,m,ans=0;//fa为并查集 
bool operator <(rec f1,rec f2)
{
    return f1.z<f2.z;
}
int get(int x)//搜索所在集合 
{
    if(x==fa[x])
    {
        return x;
    }
    return fa[x]=get(fa[x]);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i].x>>edge[i].y>>edge[i].z;
    }
    sort(edge+1,edge+1+m);//按权值从小到大排序 
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int x=get(edge[i].x);
        int y=get(edge[i].y);
        if(x==y)
        {
            continue;
        }
        fa[x]=y;//合并集合 
        ans+=edge[i].z;
    }
    cout<<ans<<endl;
    return 0;
}

②Prim算法

时间复杂度为O(n^2)
可用二叉堆优化到O(m long n)

Prim算法主要用于稠密图，特别是完全图

#include<bits/stdc++.h>
using namespace std;
const int maxn=3010;
int a[maxn][maxn],d[maxn],n,m,ans;
bool v[3010];
void prim()
{
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    d[1]=0;
    for(int i=1;i<n;i++)
    {
        int x=0;
        for(int j=1;j<=n;j++)
        {
            if(!v[j]&&(x==0||d[j]<d[x]))
            {
                x=j;
            }
        }
        v[x]=1;
        for(int y=1;y<=n;y++)
        {
            if(!v[y])
            {
                d[y]=min(d[y],a[x][y]);
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        a[i][i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        a[y][x]=a[x][y]=min(a[x][y],z);
    }
    prim();
    for(int i=1;i<=n;i++)
    {
        ans+=d[i];
    }
    cout<<ans<<endl;
    return 0;
}