连接所有点的最小费用 - LeetCode每日一题

题目描述

给你一个 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 。
注意到任意两个点之间只有唯一一条路径互相到达。

提示：

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

写在前面

根据题目要求，我们可以用points数组构建一张节点为n的连通图，任意两点之间的距离均为它们的曼哈顿距离，我们需要在这个图中获取一个极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的总权值最小。

能够满足任意两点之间有且仅有一条简单路径只有树，且这棵树包含 nn 个节点。我们称这棵树为给定的图的生成树，其中总权值最小的生成树，我们称其为最小生成树。若不懂最小生成树的同学可以我写的另一篇文章数据结构-最小生成树

最小生成树有两个非常经典的解法：Kruskal 和 Prim

方法一：Kruskal 算法

class Solution {

    class UnionFind {
        private int[] parent;
 
        public UnionFind(int N) {
            parent = new int[N];
            for (int i = 0; i < N; i++) {
                parent[i] = i;
            }
        }
    
        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }
    
        public int find(int p) {
            while (p != parent[p]) {
                p = find(parent[p]);
            }
            return parent[p];
        }
    
        public void union(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);
            if (pRoot == qRoot) {
                return;
            }
            parent[pRoot] = qRoot;
        }
    }

    private static class Edge {
        int v, e, w;

        public Edge(int v, int e, int w) {
            this.v = v;
            this.e = e;
            this.w = w;
        }
    }

    public int minCostConnectPoints(int[][] points) {
        Queue<Edge> mst = new LinkedList<>();
        Queue<Edge> pq = new PriorityQueue<>((a, b) -> {
            return a.w - b.w;
        });
        int res = 0;

        int n = points.length;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j != i && j < n; ++j) {
                pq.offer(new Edge(i, j, Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1])));
            }
        }

        UnionFind uf = new UnionFind(n);
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if (!uf.connected(cur.v, cur.e)) {
                mst.offer(cur);
                uf.union(cur.v, cur.e);
            }
        }

        while (!mst.isEmpty()) {
            Edge e = mst.poll();
            res += e.w;
        }

        return res;
    }
}

原题链接：https://leetcode-cn.com/problems/min-cost-to-connect-all-points/

Q.E.D.