最小生成树（并查集+Kruskal算法）

╰+哭是因爲堅強的太久メ 2024-04-17 18:50 33阅读 0赞

最小生成树问题（MST）是为了解决以最低的花费连接所有的点（使图的连通分量的数目为1）而提出的。

上**并查集+Kruskal算法**求解最小生成树问题的代码：

#include <cstdio>
    #include <algorithm>
    using namespace std;
    struct edge
    {
        int from;
        int to;
        int cost;
    };
    edge bian[3000];
    int f[1001];
    int n,m;
    bool cmp(edge a,edge b)
    {
        return a.cost<b.cost;
    }
    int Find(int x)
    {
        if(x==f[x])
            return x;
        else
            return f[x]=Find(f[x]);
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        int i;
        int fenliang=n;
        //初始化并查集
        for(i=1;i<=n;i++)
        {
            f[i]=i;
        }
        for(i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            bian[i].from=a;
            bian[i].to=b;
            bian[i].cost=c;
        }
        sort(bian,bian+m,cmp);
        int sum=0;
        for(i=0;i<m;i++)
        {
            int a=bian[i].from;
            int b=bian[i].to;
            int c=bian[i].cost;
            if(Find(a)==Find(b))
            {
                continue;
            }
            else
            {
                f[Find(a)]=Find(b);
                sum+=c;
                fenliang--;
            }
            if(fenliang==1)
            {
                break;
            }
        }
        if(fenliang==1)
        {
            printf("%d\n",sum);
        }
        else
        {
            printf("-1\n");
        }
        return 0;
    }

不用邻接矩阵，也不用邻接表，**用边结构存储图中顶点和边的信息**。

先**将所有的边按照权值从小到大排序**，然后遍历所有的边：如果该边连接的两个顶点不在同一个连通分量里，就把这条边加入最小生成树，并将这条边连接的两个顶点放到同一个连通分量里，连通分量的个数减1；否则继续查看下一条边。直至遍历完所有的边或者连通分量的个数变为1。

连通分量用并查集来实现，**Find(a)==Find(b)表示a和b在同一个连通分量里**，因为最初图中共有n个顶点，所以**最开始连通分量就是n，每连接一条边连通分量都会减1**。

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[20200227123106884.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/8c6d4eaa980d44fba3327011f2e61f31.jpg