关于智能合约:东哥带你刷图论第五期Kruskal-最小生成树算法

读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目：

以图判树（中等）
最低老本联通所有城市（中等）
连贯所有点的最小费用（中等）

———–

图论中知名度比拟高的算法应该就是 Dijkstra 最短门路算法，环检测和拓扑排序，二分图断定算法以及明天要讲的最小生成树（Minimum Spanning Tree）算法了。

最小生成树算法次要有 Prim 算法（普里姆算法）和 Kruskal 算法（克鲁斯卡尔算法）两种，这两种算法尽管都使用了贪婪思维，但从实现上来说差别还是蛮大的，本文先来讲 Kruskal 算法，Prim 算法另起一篇文章写。

Kruskal 算法其实很容易了解和记忆，其要害是要相熟并查集算法，如果不相熟，倡议先看下前文 Union-Find 并查集算法。

接下来，咱们从最小生成树的定义说起。

先说「树」和「图」的基本区别：树不会蕴含环，图能够蕴含环。

如果一幅图没有环，齐全能够拉伸成一棵树的模样。说的业余一点，树就是「无环连通图」。

那么什么是图的「生成树」呢，其实按字面意思也好了解，就是在图中找一棵蕴含图中的所有节点的树。业余点说，生成树是含有图中所有顶点的「无环连通子图」。

容易想到，一幅图能够有很多不同的生成树，比方上面这幅图，红色的边就组成了两棵不同的生成树：

对于加权图，每条边都有权重，所以每棵生成树都有一个权重和。比方上图，右侧生成树的权重和显然比左侧生成树的权重和要小。

那么最小生成树很好了解了，所有可能的生成树中，权重和最小的那棵生成树就叫「最小生成树」。

PS：一般来说，咱们都是在 无向加权图 中计算最小生成树的，所以应用最小生成树算法的事实场景中，图的边权重个别代表老本、间隔这样的标量。

在讲 Kruskal 算法之前，须要回顾一下 Union-Find 并查集算法。

方才说了，图的生成树是含有其所有顶点的「无环连通子图」，最小生成树是权重和最小的生成树。

那么说到连通性，置信老读者应该能够想到 Union-Find 并查集算法，用来高效解决图中联通重量的问题。

前文 Union-Find 并查集算法详解具体介绍了 Union-Find 算法的实现原理，次要使用 size 数组和门路压缩技巧进步连通重量的判断效率。

如果不理解 Union-Find 算法的读者能够去看前文，为了节约篇幅，本文间接给出 Union-Find 算法的实现：

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;}
}

前文 Union-Find 并查集算法使用介绍过 Union-Find 算法的一些算法场景，而它在 Kruskal 算法中的次要作用是保障最小生成树的合法性。

因为在结构最小生成树的过程中，你首先得保障生成的那玩意是棵树（不蕴含环）对吧，那么 Union-Find 算法就是帮你干这个事儿的。

怎么做到的呢？先来看看力扣第 261 题「以图判树」，我形容下题目：

给你输出编号从 0 到 n - 1 的 n 个结点，和一个无向边列表 edges（每条边用节点二元组示意），请你判断输出的这些边组成的构造是否是一棵树。

函数签名如下：

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

比方输出如下：

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

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

但如果输出：

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

造成的就不是树结构了，因为蕴含环：

对于这道题，咱们能够思考一下，什么状况下退出一条边会使得树变成图（呈现环）？

显然，像上面这样增加边会呈现环：

而这样增加边则不会呈现环：

总结一下法则就是：

对于增加的这条边，如果该边的两个节点原本就在同一连通重量里，那么增加这条边会产生环；反之，如果该边的两个节点不在同一连通重量里，则增加这条边不会产生环。

而判断两个节点是否连通（是否在同一个连通重量中）就是 Union-Find 算法的拿手绝活，所以这道题的解法代码如下：

// 判断输出的若干条边是否能结构出一棵树构造
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 算法就很简略了。

所谓最小生成树，就是图中若干边的汇合（咱们后文称这个汇合为 mst，最小生成树的英文缩写），你要保障这些边：

1、蕴含图中的所有节点。

2、造成的构造是树结构（即不存在环）。

3、权重和最小。

有之前题目的铺垫，前两条其实能够很容易地利用 Union-Find 算法做到，关键在于第 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 算法。

再来看看力扣第 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;
}

这道题做了一个小的变通：每个坐标点是一个二元组，那么按理说应该用五元组示意一条带权重的边，但这样的话不便执行 Union-Find 算法；所以咱们用 points 数组中的索引代表每个坐标点，这样就能够间接复用之前的 Kruskal 算法逻辑了。

通过以上三道算法题，置信你曾经把握了 Kruskal 算法，次要的难点是利用 Union-Find 并查集算法向最小生成树中增加边，配合排序的贪婪思路，从而失去一棵权重之和最小的生成树。

最初说下 Kruskal 算法的复杂度剖析：

假如一幅图的节点个数为 V，边的条数为 E，首先须要 O(E) 的空间装所有边，而且 Union-Find 算法也须要 O(V) 的空间，所以 Kruskal 算法总的空间复杂度就是 O(V + E)。

工夫复杂度次要消耗在排序，须要 O(ElogE) 的工夫，Union-Find 算法所有操作的复杂度都是 O(1)，套一个 for 循环也不过是 O(E)，所以总的工夫复杂度为 O(ElogE)。

本文就到这里，对于这种贪婪思路的简略证实以及 Prim 最小生成树算法，咱们留到后续的文章再聊。

_____________

查看更多优质算法文章点击我的头像，手把手带你刷力扣，致力于把算法讲清楚！我的算法教程曾经取得 90k star，欢送点赞！

关于智能合约:东哥带你刷图论第五期Kruskal-最小生成树算法

什么是最小生成树

Union-Find 并查集算法

Kruskal 算法

Just My Socks（注册教程内含优惠码）

关于智能合约:东哥带你刷图论第五期Kruskal-最小生成树算法

什么是最小生成树

Union-Find 并查集算法

Kruskal 算法

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）