图论算法之最小生成树Kruskal算法：关键是要熟悉Union-Find算法

最小生成树算法主要有两种：Prim算法（Prim算法）和Kruskal算法（Kruskal算法） ）。虽然这两种算法都采用了贪心思想，但它们的实现差异还是相当大的。本文会先讲Kruskal算法，Prim算法会单独写一篇文章。

克鲁斯卡尔算法实际上非常容易理解和记忆。关键是要熟悉并查算法。如果不熟悉，建议阅读之前的文章并查算法。

然后我们从最小生成树的定义开始。

什么是最小生成树？

首先我们来说说“树”和“图”的根本区别：树不包含环，但图可以包含环。

如果图像没有环，则可以将其拉伸为看起来像一棵树。更专业地说，树就是“无环连通图”。

那么什么是图的“生成树”呢？其实从字面意思上看也很容易理解。就是在图中找到一棵包含图中所有节点的树。从技术上讲，生成树是一个“非循环连接子图”，包含图的所有顶点。

很容易认为一个图像可以有许多不同的生成树。例如，在下图中，红色边形成两个不同的生成树：

对于加权图，每条边都有一个权重。所以每棵生成树都有一个权重之和。例如上图中，右侧生成树的权重之和明显小于左侧生成树的权重之和。

那么最小生成树就很容易理解了。在所有可能的生成树中，权重和最小的生成树称为“最小生成树”。

PS：一般情况下，我们计算的是无向加权图中的最小生成树，所以在实际场景中使用最小生成树算法时，图的边权值一般表示成本和距离这样的标量。

在讲Kruskal算法之前，我们需要回顾一下并查算法。

并查并查算法

正如我刚才所说，图的生成树是一个包含其所有顶点的“无环连通子图”，最小生成树是权重最小的生成树总和。

说到连通性，我想老读者都能想到并查算法，它用来高效处理图中连通分量的问题。

上一篇文章《并查并查算法详解》详细介绍了并查算法的实现原理。它主要利用size数组和路径压缩技术来提高连通分量的评估效率。

不了解并查算法的读者可以阅读上一篇文章。为了节省篇幅，本文直接提供了并查算法的实现：

class UF {
    // 连通分量个数
    private int count;
    // 存储一棵树
    private int[] parent;
    // 记录树的「重量」
    private int[] size;

    // n 为图中节点的个数
    public UF(int n) {
        this.count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    // 将节点 p 和节点 q 连通
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;

        // 小树接到大树下面，较平衡
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        // 两个连通分量合并成一个连通分量
        count--;
    }

    // 判断节点 p 和节点 q 是否连通
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    // 返回节点 x 的连通分量根节点
    private int find(int x) {
        while (parent[x] != x) {
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    // 返回图中的连通分量个数
    public int count() {
        return count;
    }
}

并查算法在上一篇文章《并查并查算法应用》中介绍了一些算法场景，以及它的主要作用Kruskal算法是为了保证最小生成树的合法性。

因为在构建最小生成树的过程中，首先要确保生成的东西是一棵树（不包含环），对吧？那么并查算法将帮助您解决这个问题。

我该怎么做？我们看一下理口第261题“看图论树”。我将描述下面的问题：

将为您提供从0到n -1s的输入号码和一个NonEdge列表，（每个边缘都表示由一个节点元组），请确定由这些输入边组成的结构是否是树。

函数签名如下：

boolean validTree(int n, int[][] edges);

例如，输入如下：

n = 5
edges = [[0,1], [0,2], [0,3], [1,4]]

这些边形成一棵树，算法应返回 true：

但是如果输入是： ，则形成的结构不是树，因为包含环：

对于这个问题我们可以想一下，什么情况下添加一条边会让树变成一个图（出现环）？

显然，添加这样的边会导致循环：

添加这样的边不会导致循环：

总结一下规则：

对于这个额外的边，如果边A节点的两侧原本在同一个连通域中，那么添加这条边就会产生环；反之，如果边的两个节点不在同一个连通域中，则添加这条边不会产生环。

判断两个节点是否连通（是否在同一个连通分量中）是并查算法的特殊之处，所以该问题的解法代码如下：

// 判断输入的若干条边是否能构造出一棵树结构
boolean validTree(int n, int[][] edges) {
    // 初始化 0...n-1 共 n 个节点
    UF uf = new UF(n);
    // 遍历所有边，将组成边的两个节点进行连接
    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        // 若两个节点已经在同一连通分量中，会产生环
        if (uf.connected(u, v)) {
            return false;
        }
        // 这条边不会产生环，可以是树的一部分
        uf.union(u, v);
    }
    // 要保证最后只形成了一棵树，即只有一个连通分量
    return uf.count() == 1;
}

class UF { 
    // 见上文代码实现
}

如果你能理解解法这个问题思路，那么掌握Kruskal算法就非常容易了。

Kruskal算法

所谓最小生成树，就是图中有几条边的集合（后面我们将这个集合称为mst，最小生成树的英文缩写）。您必须确保这些边缘：

1。包含图中的所有节点。

2。形成的结构是树结构（即没有循环）。

3。重量总和最小。

作为上一个问题的伏笔，前两个其实可以使用并查算法轻松实现。关键在于第3点，如何保证生成的生成树的权值和最小。

这里用到了贪心思想：

将所有边按权重从小到大排序，从权重最小的边开始穿越。如果这条边和mst中的其他边不会形成环，那么这条边是最小生成树的一部分，将其添加到mst集中；否则，该边不是最小生成树的一部分，请勿将其添加到mst集。

这样，最后一个mst集合中的边就形成了一棵最小生成树。让我们看一下使用 Kruskal 算法的两个示例。

第一个问题与问题1135“以尽可能低的成本连接所有城市”密切相关。这是一个标准的最小生成树问题：

每个城市对应图中的一个节点，连接城市的成本对应一条边。的权重，连接所有城市的最小成本是最小生成树的权重之和。

int minimumCost(int n, int[][] connections) {
    // 城市编号为 1...n，所以初始化大小为 n + 1
    UF uf = new UF(n + 1);
    // 对所有边按照权重从小到大排序
    Arrays.sort(connections, (a, b) -> (a[2] - b[2]));
    // 记录最小生成树的权重之和
    int mst = 0;
    for (int[] edge : connections) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];
        // 若这条边会产生环，则不能加入 mst
        if (uf.connected(u, v)) {
            continue;
        }
        // 若这条边不会产生环，则属于最小生成树
        mst += weight;
        uf.union(u, v);
    }
    // 保证所有节点都被连通
    // 按理说 uf.count() == 1 说明所有节点被连通
    // 但因为节点 0 没有被使用，所以 0 会额外占用一个连通分量
    return uf.count() == 2 ? mst : -1;
}

class UF {
    // 见上文代码实现
}

这个问题就解决了。总体思路与上一个问题非常相似。你可以把树判定算法加上按权重排序的逻辑看成是Kruskal算法。

我们看一下Likou问题1584“连接所有点的最小成本”：

例如问题中给出的例子：

points = [[0,0],[2,2],[3,10],[5,2],[7,0]]

算法应该返回20，连接点如下：

这当然也是一个标准的最小生成树问题：每个点都是无向加权图中的一个节点，边权重是曼哈顿距离，连接所有点的最小成本是权重之和最小生成树。

所以解题思路是先生成所有的边和权重，然后对这些边进行Kruskal算法：

int minCostConnectPoints(int[][] points) {
    int n = points.length;
    // 生成所有边及权重
    List<int[]> edges = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int xi = points[i][0], yi = points[i][1];
            int xj = points[j][0], yj = points[j][1];
            // 用坐标点在 points 中的索引表示坐标点
            edges.add(new int[] {
                i, j, Math.abs(xi - xj) + Math.abs(yi - yj)
            });
        }
    }
    // 将边按照权重从小到大排序
    Collections.sort(edges, (a, b) -> {
        return a[2] - b[2];
    });
    // 执行 Kruskal 算法
    int mst = 0;
    UF uf = new UF(n);
    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];
        // 若这条边会产生环，则不能加入 mst
        if (uf.connected(u, v)) {
            continue;
        }
        // 若这条边不会产生环，则属于最小生成树
        mst += weight;
        uf.union(u, v);
    }
    return mst;
}

对这道题做了一个小小的修改：每个坐标点都是一个元组，所以基于据说应该用五元组来表示加权边，但是在这种情况下执行并查算法是不切实际的；所以我们用points矩阵中的索引来表示每个坐标点，这样我们就可以直接复用之前的Kruskal的算法逻辑。

通过上面三道算法题，我想你已经掌握了Kruskal算法。主要难点是利用并查算法给最小生成树添加边，配合排序的贪心思想得到带权树。和最小的拱肩。我们来谈谈Kruskal算法的复杂度分析：

假设一张图中的节点数为V，边数为e。首先，需要。 O(E)的空间包含所有边，并查算法还需要O(V)的空间，所以Kruskal的总空间复杂度为 算法为O(V + E)。

时间复杂度主要花在排序上，需要O(ElogE)。并查算法所有操作的复杂度为 O(1)，而一个 for 循环无非就是O(E)，所以总的时间复杂度为O（ElogE）。