跳到主要内容

Kruskal算法求最小生成树

AcWing 859. Kruskal算法求最小生成树​

题目​

https://www.acwing.com/problem/content/861/ 给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。 求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。 给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。 由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

思路​

算法步骤：

  1. 初始化并查集，把n个点放在n个独立的集合
  2. 将所有的边按边权从小到大排序（贪心思想）
  3. 按顺序枚举每一条边，如果这条边连接的两个点不在同一集合，就把这条边加入最小生成树，并且合并这两个集合；如果这条边连接的两个点在同一集合，就跳过。
  4. 重复执行3，直到选取了n-1条边为止。

并查集： 当我们需要判断一个集合中的两个元素x,y是否同属于一个集合时，我们可以使用并查集的方法进行查询。 其核心思路在于将一个数组转化成一棵树的形式：每个节点初始时都认为是一棵独立的树，当两个节点同属于一个集合时，我们可以将其中一个节点指向另一个节点用于表示两个节点同属于一个集合。因此当我们想要确定两个节点是否同属于一个子集时，我们只需要比较他们二者的根节点是否相同即可。因此并查集中的基础操作有两个：find判断两个节点是否相同；合并两个相同的节点。 2、并查集实现

朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);

代码​

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N=200010;
int n,m;
int p[N];

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

int find(int x)
{
    if(p[x]!=x) return p[x]=find(p[x]);
    return p[x];
}


int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        edges[i]={a,b,w};
    }
    sort(edges,edges+m);
    for(int i=1;i<=n;i++) p[i]=i;//初始化并查集

    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)
        {
            p[a]=b;
            res+=w;
            cnt++;
        }
    }
    if(cnt<n-1) cout<<"impossible";
    else cout<<res<<endl;
    return 0;
}

0%