力扣labuladong一刷day48天Prim 最小生成树算法

力扣labuladong一刷day48天Prim 最小生成树算法

一、1135. 最低成本联通所有城市

题目链接：https://leetcode.cn/problems/connecting-cities-with-minimum-cost/
思路：本题求的就是最小生成树，使用克鲁斯卡尔也行使用普瑞姆也行，之前使用克鲁斯卡尔即利用并查集排序后按照最小代价进行连接。
今天我使用普瑞姆来解题。

主要思路是选取一个点，从这个点开始保留权重最小的边，然后把权重最小的边所连接的点作为最小生成树中的第二个点，然后再去找与它相连接的边中权重最小的，以此往复。

结论是也能做，但是明显内存占用更多，虽然时间是一个量级，但其他操作更多，占用也多。

class Solution {
    public int minimumCost(int n, int[][] connections) {
        List<int[]>[] graph = new ArrayList[n+1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] ints : connections) {
            int u = ints[0], v = ints[1], w = ints[2];
            graph[u].add(new int[]{u, v, w});
            graph[v].add(new int[]{v, u, w});
        }
        Prim prim = new Prim(graph);
        if (!prim.isConnected()) return -1;
        return prim.sum;
    }

    class Prim {

        int sum;
        boolean[] isVisited;
        List<int[]>[] graph;
        PriorityQueue<int[]> pq;

        public Prim(List<int[]>[] graph) {
            this.graph = graph;
            this.pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
            int n = graph.length;
            isVisited = new boolean[n];

            isVisited[1] = true;
            cat(1);

            while (!pq.isEmpty()) {
                int[] ints = pq.poll();
                int to = ints[1];
                if (isVisited[to]) continue;

                isVisited[to] = true;
                sum += ints[2];

                cat(to);
            }

        }

        void cat(int i) {
            for (int[] ints : graph[i]) {
                if (isVisited[ints[1]]) continue;
                pq.add(ints);
            }
        }


        boolean isConnected() {
            for (int i = 1; i < isVisited.length; i++) {
                if (!isVisited[i]) return false;
            }
            return true;
        }
    }
}

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

题目链接：https://leetcode.cn/problems/min-cost-to-connect-all-points/
思路：本题思路和上一题基本一致，就是构建好prim算法，然后构建邻接表。但我还更喜欢用并查集一些，一方面更快，另一方面代码简洁。
拓展了一下思路也还行吧。

class Solution {
   public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = 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];
                int w = Math.abs(xi - xj) + Math.abs(yi - yj);
                graph[i].add(new int[]{i, j, w});
                graph[j].add(new int[]{j, i, w});
            }
        }
        Prim prim = new Prim(graph);
        return prim.sum;
    }

    class Prim{

        int sum;
        boolean[] visited;
        List<int[]>[] graph;
        PriorityQueue<int[]> pq;

        public Prim(List<int[]>[] graph) {
            this.graph = graph;
            int n = graph.length;
            visited = new boolean[n];
            pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);

            visited[0] = true;
            cut(0);

            while (!pq.isEmpty()) {
                int[] ints = pq.poll();
                int to = ints[1];
                if (visited[to]) continue;
                sum += ints[2];
                visited[to] = true;
                cut(to);
            }
        }

        void cut(int i) {
            for (int[] ints : graph[i]) {
                if (visited[ints[1]]) continue;
                pq.add(ints);
            }
        }

        boolean isConnected() {
            for (int i = 0; i < visited.length; i++) {
                if (!visited[i]) return false;
            }
            return true;
        }
    }
}