LeetCode/1584. 连接所有点的最小费用

1584. 连接所有点的最小费用

给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

示例 1：

输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：

我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。

示例 2：

输入：points = [[3,12],[-2,5],[-4,1]]
输出：18

示例 3：

输入：points = [[0,0],[1,1],[1,0],[-1,1]]
输出：4

示例 4：

输入：points = [[-1000000,-1000000],[1000000,1000000]]
输出：4000000

示例 5：

输入：points = [[0,0]]
输出：0

提示：

• 1 <= points.length <= 1000
• -106 <= xi, yi <= 106
• 所有点 (xi, yi) 两两不同。

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

最小生成树相信大家在学习数据结构的时候都学习过，两种经典的算法：Kruskal（加边法）和Prim（加点法），思路也很简单，Kruskal就是在整个图中每次寻找最小的边加入结果集，最终形成路径和最短的树，而Prim算法就是维护一个邻接数组，每次在图中选出一个离最小生成树路径最短的点加入最小生成树中，直至最后所有点都在最小生成树中。

虽然思路简单，但是写起代码来其实并不是那么容易，首先介绍Kruskal算法。具体代码如下：

class Solution {
    public int minCostConnectPoints(int[][] points) {
        //结点的个数
        int n = points.length;
        DisjointSetUnion dsu = new DisjointSetUnion(n);
        List<Edge> edges = new ArrayList<>();
        //计算所有的边
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                edges.add(new Edge(dist(points, i, j), i, j));
            }
        }
        //按照边的大小由小到大排序
        Collections.sort(edges, Comparator.comparingInt(edge -> edge.len));
        int ret = 0, num = 1;
        //遍历所有的边
        for (Edge edge : edges) {
            int len = edge.len, x = edge.x, y = edge.y;
            //判断两条边是否连通，即是否有同一个父节点，如果是直接跳过
            //如果不是，则将边加入最小生成树，更新ret和num
            if (dsu.unionSet(x, y)) {
                ret += len;
                num++;
                if (num == n) {
                    break;
                }
            }
        }
        return ret;
    }

    //计算两点之间的曼哈顿距离
    public int dist(int[][] points, int x, int y) {
        return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
    }
}

//并查集实现
class DisjointSetUnion {
    int[] f;
    int[] rank;
    int n;

    public DisjointSetUnion(int n) {
        this.n = n;
        this.rank = new int[n];
        Arrays.fill(this.rank, 1);
        this.f = new int[n];
        for (int i = 0; i < n; i++) {
            this.f[i] = i;
        }
    }

    //查
    public int find(int x) {
        return f[x] == x ? x : (f[x] = find(f[x]));
    }

    //并
    public boolean unionSet(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) {
            return false;
        }

        if (rank[fx] < rank[fy]) {
            int temp = fx;
            fx = fy;
            fy = temp;
        }

        rank[fx] += rank[fy];
        f[fy] = fx;
        return true;
    }
}

//定一个边，包括长度、起始点和终止点
class Edge {
    int len, x, y;

    public Edge(int len, int x, int y) {
        this.len = len;
        this.x = x;
        this.y = y;
    }
}

Prim算法就是通过维护一个邻接矩阵，里面存放的两点之间的曼哈顿距离，最开始随机选一个点加入最小生成树中，然后更新该点到其他剩余各点的距离，每次选出离最小生成树最近的点加入最小生成树中。具体代码如下：

class Solution {
    public int minCostConnectPoints(int[][] points) {
        return prim(points, 0);
    }

    private int prim(int[][] points, int start) {
        int n = points.length;
      	//如果只有一个点，则最小距离和为0
        if (n < 2) return 0;
        int result = 0;

      	//构建邻接矩阵，里面存放每两点之间的距离
        int[][] grap = new int[n][n];
      	//初始化所有点的之间的距离
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = dist(points, i, j);
                grap[i][j] = temp;
                grap[j][i] = temp;
            }
        }


      	//用于记录当前点到其他点之间的最小距离
        int[] lowCost = new int[n];
        Arrays.fill(lowCost, Integer.MAX_VALUE);
      	//用于记录当前点是否已经加入到最小生成树当中，0表示已经加入，-1表示未加入
        int[] visited = new int[n];
        Arrays.fill(visited, -1);

      	//这里默认以第一个点为开始
        visited[start] = 0;
      	//更新第一个点到其他点的最近距离
        for (int i = 0; i < n; i++) {
            if (i == start) continue;
            lowCost[i] = grap[i][start];
        }

        for (int i = 1; i < n; i++) {
            int minIndex = -1;
            int minValue = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
              	//如果已经加入最小生成树了，直接跳过
                if (visited[j] == 0) continue;
              	//找出离最小生成树最近的，未加入最小生成树的点的索引和值
                if (lowCost[j] < minValue) {
                    minIndex = j;
                    minValue = lowCost[j];
                }
            }

          	//记录最小路径和
            result += minValue;
          	//标记该点已经访问
            visited[minIndex] = 0;
            lowCost[minIndex] = -1;

          	//更新邻接矩阵中的路径
            for (int j = 0; j < n; j++) {
                if (visited[j] == -1 && grap[j][minIndex] < lowCost[j]) {
                    lowCost[j] = grap[j][minIndex];
                }
            }
        }

      	//遍历完成后
        return result;
    }

  	//计算两点之间的曼哈顿距离
    private int dist(int[][] points, int x, int y) {
        return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
    }
}

写在最后：

Kruskal算法和Prim算法是数据结构中非常经典的算法，只要跟着算法思路走下来，虽然繁琐，但是没有特别难理解的地方，建议小伙伴们这两个算法与Dijkstra算法和Floyd算法结合起来学习，前两个是找最小生成树，后两个是找最短路径，Kruskal和Dijkstra从边入手，Prim和Floyd是从点入手。