1584. 连接所有点的最小费用（中等）

图论中知名度比较高的算法应该就是 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 算法就是帮你干这个事儿的。
 
 
怎么做到的呢？先来看看力扣第 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 算法就很简单了。
 
 
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 最小生成树算法，我们留到后续的文章再聊。
 
 
-----------
 
 
最后帮朋友打个广告，刘欣（@码农翻身）的新书《半小时漫画计算机》出版了，不仅和他的第一本书《码农翻身》一脉相承，浅显易懂，而且这次更绝，用漫画表现计算机技术，趣味性很强，你值得拥有！
 
给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
给定一张边带权的无向图G=(V,E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。
由V中的全部n个顶点和E中n−1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。
【输入格式】
第一行包含两个整数n和m。
接下来m行，每行包含三个整数u,v,w，表示点u和点v之间存在一
他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。
约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。
约翰的农场的编号是1，其他农场的编号是 2∼n。
为了使花费最少，他希望用于连接所有的农场的光纤总长度尽可能短。
你将得到一份各农场之间连接距离的列表，你必须找出能连接所有农场并使所用光纤最短的方案。
第一行包含一个整数...
                                    对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。
该图包含n个节点，标记为0到n - 1。给定数字n和一个无向边edges列表（每一个边都是一对标签）。
你可以假设没有重复的边会出现在edges中。由于所有的边都是无...
求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。
由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无...
Prim算法，Kruskal算法，以及Reverse-Delete algorithm（反向删除算法）
prim算法适合稠密图，kruskal算法适合简单图。
下面来用Kruskal算法实现最小生成...
                                    Problem Description
某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
 Input
本题目包含多组数据，请处理到文件结束。
每组数据第一行包
要求对一个图使用kruskal算法求最小生成树，依次输出选出的边所关联的顶点序列，要求下标较小者在前，如图所示，其顶点序列为1 3 4 6 2 5 3 6 2 3
若干行整数
第一行为两个整数，分别为图的顶点数和边数
第二行开始是该图的邻接矩阵，主对角线统一用0表示，无直接路径的两点用100来表示（保证各边权值小于100）
若干用空格隔开的整数
0 6 1 ...
我们可以使用Kruskal的最小生成树算法（一种贪婪算法）为连接的加权图找到最小生成树。Kruskal算法的工作原理是，从给定图中找到覆盖图中存在的每个顶点的...
                                    Kruskal最小生成树生成树 已知连通图G ，图上有N个顶点。生成树是指图G的一个极小（边最少）连通子图，生成树上有n个顶点、n-1条边，且任意两点之间都是连通的。 最小生成树 已知带权连通图G，图中有n个顶点，每条边都有权值。我们要从图中抽出一棵生成树，使得树上所有边权之和最小，这棵生成树就叫做 最小生成树。 常见变形应用： 1.要求找最大边权是最小的的生成树（多读几遍）：直接找最小生成树即可...