图论 最小生成树

普利姆算法(prim)

朴素版 稠密图常用 O(n^2)

借助临界矩阵存储g[N][N]

const int INF=0x3f3f3f3f;
int prim(){
    int res=0;//最小生成树的距离
    memset(dist,0x3f,sizeof(dist));

    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j]){
                t=j;
            }
        }
        //不是第一个点且到集合的距离为INF 说明与集合不相连
        if(i&&dist[t]==INF){
            return INF;
        }
        if(i){
            res+=dist[t];
        }
        //拓展其他节点到集合的距离
        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],g[t][j]);
        }
        st[t]=true;//将该点加入集合
    }
    return res;
}
int main(){
    memset(g,0x3f,sizeof(g));
    cin>n>>m;
    while(m--){
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    int t=prim();
    if(prim==INF){
        cout<<"impossible<<endl;
    }
    else{
        cout<<t<<endl;
    }
    return 0;
}

堆优化版O(m*logn)

不常用

克鲁斯卡尔算法(Kruskal)

稀疏图常用 O(m*logm)

①将所有边按权重从小到大排序O(m*logn)
②枚举每条边a b和权重c
if(a b不连通){
将a b这条边加入集合中
}

//排序
struct Edge{
    int a,b,w;
    bool operator<(const Edge &W){
        return w<W.w;
    }
}edges[N];

sort(edges,edges+m);

//并查集初始化
for(int i=1;i<=n;i++){
    p[i]=i;
}
int find(int x){
    if(p[x]!=x){
        p[x]=find(f[x]);
    }
    return p[x];
}

//枚举每条边
int res=0,cnt=0;
for(int i=0;i<m;i++){
    int a=edges[i].a,b=edges[i].b,w=edges[i].w;
    a=find(a),b=find(b);
    if(a!=b){
        f[a]=b;
        res+=w;
        cnt++;
    }
}
//输出
if(cnt!=n-1){//n个节点的最小生成树 有n-1条边
    puts("impossible);
}
else{
    cout<<res<<endl;
}