侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

【最小生成树, Kruskal算法, Prim算法】连接所有点的最小费用

GabrielxD
2022-05-31 / 0 评论 / 0 点赞 / 346 阅读 / 2,136 字
温馨提示:
本文最后更新于 2022-11-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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


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

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

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

示例 1:

image-20220530191832704

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

image-20220530191846734

我们可以按照上图所示连接所有点得到最小总费用,总费用为 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
  • -10^6 <= xi, yi <= 10^6
  • 所有点 (xi, yi) 两两不同。

解题

前置知识

  • 生成树生成树 指的是「无向图」中,具有该图的 全部顶点边数最少连通子图
  • 最小生成树最小生成树 指的是「加权无向图」中总权重最小的生成树。
  • 切分:
    image-20220530192616767
  • 切分定理:在一幅连通加权无向图中,给定任意的切分,如果有一条横切边的权值严格小于所有其他横切边,则这条边必然属于图的最小生成树中的一条边。

方法一:Kruskal算法 并查集 优先队列

思路

本题是典型的最小生成树应用题。

Kruskal 算法:是求解「加权无向图」的「最小生成树」的一种算法。

具体做法:

  1. 把图中所有边按照从小到大排序。
  2. 把边依次加入最小生成树,如果形成环就跳过。
  3. 直到选择 N-1 条边为止(N 指顶点数)。

在本题中:共有 n=len(points)n=len(points) 个点,有 n(n1)2\frac{n(n-1)}{2} 条边可供选择。对于点 (i,j)(i,j),连接它们的边的权值为 points[i][0]points[j][0]+points[j][1]points[j][1]|points[i][0] - points[j][0]| + |points[j][1] - points[j][1]|

那么我们就可以使用一个优先队列(priQueue)来存储每条边并把它们按照其权值排序。再维护一个并查集(uf)用于在添加某条边之前,确定其连接的两个点之前是否会形成环(isConnected())。

循环从优先队列中取出边:

  • 如果当前边连接的两个顶点会形成环,则跳过本次循环。
  • 否则使用并查集合并这两个顶点,边的计数(count)自增,答案(ans)加上该边的权重值。
  • 如果 count == n-1 或者优先队列为空就退出循环。

代码

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        Queue<Edge> priQueue = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int weight = Math.abs(points[i][0] - points[j][0]) +
                    Math.abs(points[i][1] - points[j][1]);
                priQueue.add(new Edge(i, j, weight));
            }
        }
        UnionFind uf = new UnionFind(n);
        int ans = 0, count = 0;
        while (!priQueue.isEmpty() && count < n - 1) {
            Edge curr = priQueue.poll();
            if (uf.isConnected(curr.v1, curr.v2)) continue;
            uf.union(curr.v1, curr.v2);
            count++;
            ans += curr.weight;
        }
        return ans;
    }

    static class Edge implements Comparable<Edge> {
        public int v1;
        public int v2;
        public int weight;

        public Edge(int v1, int v2, int weight) {
            this.v1 = v1;
            this.v2 = v2;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge e) {
            return Integer.compare(this.weight, e.weight);
        }
    }

    static class UnionFind {
        public int groups;
        private int[] root;
        private int[] rank;

        public UnionFind() {}
        
        public UnionFind(int size) {
            groups = size;
            root = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                root[i] = i;
                rank[i] = 1;
            }
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;
            if (rank[rootP] > rank[rootQ]) {
                root[rootQ] = rootP;
            } else if (rank[rootP] < rank[rootQ]) {
                root[rootP] = rootQ;
            } else {
                root[rootQ] = rootP;
                rank[rootP]++;
            }
            groups--;
        }
        
        public int find(int n) {
            return n == root[n] ? n : (root[n] = find(root[n]));
        }
        
        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }
    }
}

Kruskal模板

class Solution {
    static class Edge implements Comparable<Edge> {
        int u, v, w;
        
        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Edge e) {
            return this.w - e.w;
        }
    }

    static final int INF = 0x3f3f3f3f;
    int n, m;
    Edge[] edges;
    int[] roots;

    int find(int x) {
        return roots[x] == x ? x : (roots[x] = find(roots[x]));
    }

    void union(int p, int q) {
        roots[find(p)] = find(q);
    }

    int kruskal() {
        Arrays.sort(edges);
        roots = new int[n];
        for (int i = 0; i < n; ++i) roots[i] = i;
        int cnt = 0, res = 0;
        for (Edge edge : edges) {
            int u = edge.u, v = edge.v, w = edge.w;
            if (find(u) != find(v)) {
                union(u, v);
                res += w;
                if (++cnt == n - 1) break;
            }
        }
        return cnt < n - 1 ? INF : res;
    }

    public int minCostConnectPoints(int[][] points) {
        n = points.length;
        m = n * (n - 1) / 2;
        edges = new Edge[m];
        for (int i = 0, u = 0; u < n; ++u) {
            for (int v = u + 1; v < n; ++v) {
                int w = Math.abs(points[u][0] - points[v][0]) +
                    Math.abs(points[u][1] - points[v][1]);
                edges[i++] = new Edge(u, v, w);
            }
        }
        return kruskal();
    }
}

方法二:朴素Prim算法

思路

读题目可以看出这是稠密图求最小生成树,故可以使用:最小生成树 - 朴素Prim模板 求解。

由于所有顶点两两之间都有一条边且不存在重边和自环,所以可以省去初始化的操作直接构造邻接矩阵。

代码

class Solution {
    static final int INF = 0x3f3f3f3f;
    int n;
    int[][] g;

    int prim() {
        int[] dists = new int[n];
        Arrays.fill(dists, INF);
        boolean[] vis = new boolean[n];
        int res = 0;
        for (int i = 0; i < n; ++i) {
            int min = -1;
            for (int j = 0; j < n; ++j) {
                if (!vis[j] && (min == -1 || dists[j] < dists[min])) min = j;
            }
            if (i != 0) {
                if (dists[min] == INF) return INF;
                res += dists[min];
            }
            vis[min] = true;
            for (int j = 0; j < n; ++j) dists[j] = Math.min(dists[j], g[min][j]);
        }
        return res;
    }

    public int minCostConnectPoints(int[][] points) {
        n = points.length;
        g = new int[n][n];
        for (int u = 0; u < n; ++u) {
            for (int v = u + 1; v < n; ++v) {
                int w = Math.abs(points[u][0] - points[v][0]) +
                    Math.abs(points[u][1] - points[v][1]);
                g[u][v] = g[v][u] = w;
            }
        }
        return prim();
    }
}

方法三:堆优化Prim算法 优先队列

思路

Kruskal 算法步骤:

  • 维护两个集合:visited 访问过的顶点,non-visited 未访问过的顶点。
  • 每次从 non-visited 选出一个顶点放入 visited ,把 visited 中的顶点看作一个整体,选出它与外界连接的边中,权重最小的一个,这个边就是最小生成树的一个组成部分,这个边连接的另一个节点就是下一次要从 non-visited 中选出的顶点。

在本题中,维护一个用于存未访问过顶点的优先队列(priQueue),一个用于标识那些顶点是被访问过了的的数组(visited)。
先把 visited[0] 标为 true 表示选择了先访问第一个顶点 0,随后把顶点 0 与外界连接的边全部加入优先队列中。
循环从优先队列中取出边:

  • 如果当前边(curr)所连接的另一个顶点已经被访问过了,就跳过本次循环。
  • 否则,curr 就是 visited最新加入的顶点与外界连接的边中权重最小的,边的计数(count)自增,答案(ans)加上 curr 的权重值,
    再在 visited 中把 curr 标记为已访问,内循环把所有顶点 curr 与外界连接的边全部加入优先队列,然后进行下一次循环。
  • 如果 count == n-1 或者优先队列为空就退出循环。

代码

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        Queue<Edge> priQueue = new PriorityQueue<>();
        for (int i = 1; i < n; i++) {
            int weight = Math.abs(points[0][0] - points[i][0]) +
                Math.abs(points[0][1] - points[i][1]);
            priQueue.add(new Edge(0, i, weight));
        }
        boolean[] visited = new boolean[n];
        visited[0] = true;
        int ans = 0, count = 0;
        while (!priQueue.isEmpty() && count < n - 1) {
            Edge curr = priQueue.poll();
            int vertex = curr.v2;
            if (visited[vertex]) continue;
            ans += curr.weight;
            count++;
            visited[vertex] = true;
            for (int i = 0; i < n; i++) {
                if (visited[i]) continue;
                int weight = Math.abs(points[vertex][0] - points[i][0]) +
                    Math.abs(points[vertex][1] - points[i][1]);
                priQueue.add(new Edge(vertex, i, weight));
            }
        }
        return ans;
    }

    static class Edge implements Comparable<Edge> {
        public int v1;
        public int v2;
        public int weight;

        public Edge(int v1, int v2, int weight) {
            this.v1 = v1;
            this.v2 = v2;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge e) {
            return Integer.compare(this.weight, e.weight);
        }
    }
}
0

评论区