1584. Min Cost to Connect All Points - Medium

前往題目

思路

有兩種主要做法:

• prim’s
• Kruskal’s

Prim’s(使用PQ)

1. 循環直到全部的點都走過
2. 在循環裡，每次都從pq取出並查看是否已經走過，否則加入走過的點並把當前weight加入結果
3. 每次都把該點所有的邊(與尚未走過的點)都加入pq

因為一開始起始點是0，保證最小值，接下來加入pq時會自動由小到大排序，所以保證永遠都取到最小的邊

Kruskal’s(使用Union-Find)

1. 初始化每個點的爸爸都是自己
2. 運用pq把每條邊都加入(pq放入距離，起始點與終點)
3. 循環直到取了n-1條邊
4. 每次循環都判斷兩點是否已經連通，沒有的話連上並且加入結果

Code

Prim’s

class Solution {
    public int minCostConnectPoints(int[][] points) {
        // {weight, index}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, 0});

        // Amount of points
        int n = points.length;
        Set<Integer> visited = new HashSet<>();
        int res = 0; // Total cost

        while (visited.size() < n) {
            int[] arr = pq.poll();
            
            int weight = arr[0];
            int currNode = arr[1];

            // Skip if exists
            if (visited.contains(currNode)) continue;

            visited.add(currNode);
            res += weight;

            // Adding other nodes that haven't been visited to the queue
            for (int nextNode = 0; nextNode < n; ++nextNode) {
                if (!visited.contains(nextNode)) {
                    int nextWeight = Math.abs(points[nextNode][0] - points[currNode][0]) + 
                                     Math.abs(points[nextNode][1] - points[currNode][1]);
                    pq.offer(new int[]{nextWeight, nextNode});
                }
            }
        }
        return res;
    }
}

Kruskal’s

class Solution {
    int[] father = new int[1000];

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        // Init. fathers
        for (int i = 0; i < n; ++i) {
            father[i] = i;
        }

        // Min heap
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int dis = Math.abs(points[i][0] - points[j][0]) +
                        Math.abs(points[i][1] - points[j][1]);
                // Adding weight, start, end point
                pq.offer(new int[] { dis, i, j });
            }
        }

        int res = 0;
        int count = 1;
        while (count < n) {
            int[] edge = pq.poll();
            int a = edge[1];
            int b = edge[2];
            int dis = edge[0];
            // When a and b haven't connected
            if (findFather(a) != findFather(b)) {
                Union(a, b);
                ++count;
                res += dis;
                if (count == n)
                    break;
            }
        }
        return res;
    }

    private int findFather(int x) {
        // Itself's father should be itself
        // if not, find again through it's father
        if (father[x] != x)
            father[x] = findFather(father[x]);
        return father[x];
    }

    private void Union(int x, int y) {
        x = father[x];
        y = father[y];
        // Make them the same father
        if (x < y)
            father[y] = x;
        else
            father[x] = y;
    }
}