Kruskal算法--最小生成树

Kruskal算法，用来求解「加权连通图」的最小生成树，适用「稀疏图」

区别于Prim算法，Kruskal算法基于边集，维持一个边的集合

Kruskal算法

$n$ 代表顶点数量，$m$ 代表边的数量

平均时间复杂度为 $\Omicron(m\log n)$

算法流程

① 构造一个新图 $G_{new}$，包含原图 $G$ 所有的顶点，但是不含任何边

② 将 $G$ 所有的边按照权重从小到大排序 $\Omicron(m\log m)$

③ 枚举每条边 $edge<a\to b>$

• 如果在新图 $G_{new}$ 中，顶点 $a$ 和 $b$ 是不连通的
• 则将 $edge<a\to b>$ 加入 $G_{new}$ 中

算法分析

使用并查集

算法第三步中，判断两个顶点是否连通和将边加入集合中

都可以使用并查集来做，时间复杂度是 $\Omicron(1)$ 的

参考连通块中点的数量|并查集-acwing算法基础课笔记

• 判断顶点 $a$ 和 $b$ 是否连通 $\iff$ 判断 $a$ 和 $b$ 是否有同一个祖先
• 将边 $edge<a\to b>$ 加入 $G_{new}$ $\iff$ 在 $a$ 和 $b$ 之间连一条边: 可以按秩合并

关于时间复杂度

边按权重排序，理论上是最慢的一步，虽然时间复杂度是 $m\log m$ 级别的，但是核心代码执行次数前面的常数系数较小，实际效率很不错

计算时间复杂度时

执行次数最多的语句，看做核心代码

不严谨地说，「核心代码执行次数的量级」就是时间复杂度

假设：一个算法核心代码执行次数为 $98\times n(n$-$1)$

则其时间复杂度应为 $\Omicron(n^2)$

$\lim_{x\rightarrow \infty } \frac{98n(n-1)}{n^2}=98=k$

$k$ 即为那个常数系数

代码实现

核心代码

static int kruskal() {
    // 先按照权值排序
    Arrays.sort(edges, 0, m, (a, b) -> {
        return a[0] - b[0];
    });
    // 初始化
    for (int i = 1; i <= n; ++i) {
        p[i] = i;
        rank[i] = 1;
    }
    int res = 0, cnt = 0;
    for (int i = 0; i < m; ++i) {
        int a = edges[i][1];
        int b = edges[i][2];
        int c = edges[i][0];
        // 祖宗节点不同，则不在同一个连通块中
        if (find(a) != find(b)) {
            cnt++;
            merge(a, b);
            res += c;
        }
    }
    // 加入的节点少于n-1，说明存在其他连通分量
    return cnt < n - 1 ? INF : res;
}

关于「路径压缩」和「按秩合并」的实现参见完整代码👇🏻

java版完整代码

acwing 859. Kruskal算法求最小生成树

给定一个 $n$ 个点 $m$ 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围 $1\le n\le 10^5,\ 1\le m \le 2\times10^5$，为稀疏图

import java.util.*;
import java.io.*;

class Main {
    static final int INF = 0x3f3f3f3f;
    static final int N = 100010;
    static final int M = 200010;
    static int[] p = new int[N];
    static int[] rank = new int[N];
    static int[][] edges = new int[M][3];
    static int n, m;
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    // 路径压缩
    static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    // 按秩合并
    static void merge(int _a, int _b) {
        int a = find(_a), b = find(_b); // 先保存下来a和b的根节点
        if (rank[a] <= rank[b]) {
            p[a] = b; // 将秩小的根挂到秩较大的根节点上面
        } else {
            p[b] = a;
        }
        // 考虑两个集合秩相同的情况下，合并会导致深度加一
        if (rank[a] == rank[b] && a != b) {
            rank[b]++;
        }
    }

    static int kruskal() {
        // 先按照权值排序
        Arrays.sort(edges, 0, m, (a, b) -> {
            return a[0] - b[0];
        });
        // 初始化
        for (int i = 1; i <= n; ++i) {
            p[i] = i;
            rank[i] = 1;
        }
        int res = 0, cnt = 0;
        for (int i = 0; i < m; ++i) {
            int a = edges[i][1];
            int b = edges[i][2];
            int c = edges[i][0];
            // 祖宗节点不同，则不在同一个连通块中
            if (find(a) != find(b)) {
                cnt++;
                merge(a, b);
                res += c;
            }
        }
        // 加入的节点少于n-1，说明存在其他连通分量
        return cnt < n - 1 ? INF : res;
    }

    public static void main(String[] args) throws Exception {
        String[] str = cin.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        int a, b, c;

        for (int i = 0; i < m; ++i) {
            str = cin.readLine().split(" ");
            a = Integer.parseInt(str[0]);
            b = Integer.parseInt(str[1]);
            c = Integer.parseInt(str[2]);

            edges[i][0] = c;
            edges[i][1] = a;
            edges[i][2] = b;
        }
        int ans = kruskal();
        if (ans == INF) log.write("impossible\n");
        else log.write(String.valueOf(ans));

        log.flush();
        log.close();
        cin.close();
    }
}

参考资料

• 克鲁斯克尔算法|Wiki

• 最小生成树|OI Wiki