Kruskal 最小生成树算法

· · 算法·理论

最小生成树

一个图的子图中边权和最小的树称为最小生成树。

所以，如果一张子图是最小生成树，那么一定满足下列条件：

Kruskal 算法

前言和优点介绍

Kruskal 算法是一种用来寻找最小生成树的算法，由 Joseph Kruskal 在 1956 年发表。用来解决同样问题的还有 Prim 算法和 Boruvka 算法等，三种算法都是贪心算法的应用。Kruskal 算法在图中存在相同权值的边时也仍然有效。

kruskal 算法是竞赛中最常用的最小生成树算法（相较于 prim 算法而言），原因有下：

思路

算法的具体步骤为：

我们先假设最终的要生成的最小生成树为子图 G'，原图称为 G。

  1. 将图 G 中所有边依次加入集合中。初始假定图 G' 中所有点相互独立。
  2. 取出集合中边权最小的边，判断边的两断电在 G' 中是否联通。
  3. 如果联通说明两个点已经有其它边将两点联通了，那么跳过这条边，如果不连通，说明这条边属于最小生成树，将这条边加入 G' 之中。
  4. 重复 2，3 操作直到集合为空。此时被选择的边构成最小生成树。

★ 那么，问题来了，如何快速查找最短边呢？如何判断两个点在子图中是否连通呢？

可以将所有边放入优先队列（按权值从小到大排序），这样一来就可以实现 \log n 查询最小边了。
而在 kruskal 中，我们不需要动态最小值，所以 sort 也可以进行排序。

判断联通可以使用并查集，并查集每次合并和查询的时间复杂度为 \operatorname{Ackermann}^{-1}(n)，即阿克曼函数的反函数的时间复杂度，可以忽略为常数。

正确性证明

Kruskal 算法的本质，就是开始时将所有点看为独立的树，在整个过程中不停的找到最短的边，其两端连接的树没有被合并，就将其合并在一起，我们要证明的，是对于整张图 G，对于点集 A 和 B，满足 A\cap B=\empty，假设 T_A 为 A 的最小生成树，T_B 为 B 的最小生成树，且 \exist e(u,v)\in G，u\in A，v\in B，选择所有连接 A 和 B 之间的边 e 中最小的，将 T_A 和 T_B 两棵生成树合并，需要证明的是，这样的选择得到的新生成树 T_{A\cup B}=T_A\cup T_B\cup {e} 对于点集 A\cup B 生成树中是最小的一个。

从结果论的角度考虑，对于生成树 T_{A\cup B}，一定可以拆成 T_A、T_B 和一条边 {e} 的形式，那么若 T_A 和 T_B 确定，很显然 e 应当是所有连接 A 和 B 中点的边中最小的那条。

适用范围

因为 kruskal 算法时间复杂度为 m\log m，相比于时间复杂度为 m \log n 的 Prim 算法，在稀疏图中会效果更好，但由于 \log_2 n 和 \log_2 m 的差距非常小，可以忽略。

但是在极端条件和极端数据下，稠密图中，一般选择 Prim 算法，但在 n,m\leq 5\times 10^5 的数据中，通常两种算法都可过。

kruskal 算法代码

我自己还是喜欢用 sort 版，因为效率会更高一些。

// kruskal 最小生成树算法
// priority_queue 版
#include <bits/stdc++.h>

using namespace std;

const int N=5e3+4,M=2e5+4;

int n,m;
int res,ct;
int fa[N];

int find(int id) {
    return (fa[id]==id)?id:(fa[id]=find(fa[id]));
}
void merge(int a,int b) {
    fa[find(a)]=fa[find(b)];
}

vector<pair<int,int>> g[M];
priority_queue<pair<int,pair<int,int>>> pq;

void read() {
    cin>>n>>m;
    for(int i=1,st,ed,wt;i<=m;++i) {
        cin>>st>>ed>>wt;
        g[st].push_back({ed,wt});
    }
}

void kruskal() {
    for(int i=1;i<=n;++i) fa[i]=i;

    for(int i=1;i<=n;++i)
        for(auto c:g[i])
            pq.push(make_pair(-c.second,make_pair(i,c.first)));
    while(pq.size()) {
        auto c=pq.top();
        pq.pop();
        int st=c.second.first;
        int ed=c.second.second;
        int wt=-c.first;
        if(find(st)==find(ed)) continue;
        res+=wt,ct++;
        merge(st,ed);
    }

    if(ct!=n-1) cout<<"orz\n";
    else cout<<res<<'\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    read();
    kruskal();

    return 0;
}
// kruskal 最小生成树算法
// sort 版
#include <bits/stdc++.h>

using namespace std;

const int N=5e3+4,M=2e5+4;

int n,m;
int res,ct;
int fa[N];

int find(int id) {
    return (fa[id]==id)?id:(fa[id]=find(fa[id]));
}
void merge(int a,int b) {
    fa[find(a)]=fa[find(b)];
}

vector<pair<int,int>> g[M];
vector<pair<int,pair<int,int>>> q;

void read() {
    cin>>n>>m;
    for(int i=1,st,ed,wt;i<=m;++i) {
        cin>>st>>ed>>wt;
        g[st].push_back({ed,wt});
    }
}

void kruskal() {
    for(int i=1;i<=n;++i) fa[i]=i;

    for(int i=1;i<=n;++i)
        for(auto c:g[i])
            q.push_back(make_pair(c.second,make_pair(i,c.first)));
    sort(q.begin(),q.end());
    for(int i=0;i<q.size();++i) {
        auto c=q[i];
        int st=c.second.first;
        int ed=c.second.second;
        int wt=c.first;
        if(find(st)==find(ed)) continue;
        res+=wt,ct++;
        merge(st,ed);
    }

    if(ct!=n-1) cout<<"orz\n";
    else cout<<res<<'\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    read();
    kruskal();

    return 0;
}

练习题

模板题：https://www.luogu.com.cn/problem/P3366。

使用以上模板代码可以直接AC（但是请不要抄袭）。

洛谷官方最小生成树题单：https://www.luogu.com.cn/training/209。

prim 算法最小生成树。