題目網址：https://leetcode.cn/problems/min-cost-to-connect-all-points/

題意：給一整數 array points, 表示 2D 平面上的一些點, 其中 points[i] = [x_i, y_i] 。

連接點 [x_i, y_i] 和點 [x_j, y_j] 的費用為它們之間的曼哈頓距離：

  • |x_i - x_j| + |y_i - y_j|

其中 |val| 表示 val 的絕對值。

返回將所有點連接的最小總費用。

Solution 1：

想法：本題其實就是在求 MST (Minimum Spaning Tree), 故利用 Kruskal 演算法, 每次選擇 cost 最小的邊 e, 若加入 e 會導致 graph 中有 cycle（用 Union Find 判斷）, 則跳過 e, 直到 graph 中有 n - 1 條邊

typedef tuple<int, int, int> t3i;

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        const int n = points.size();
        vector<int> parents(n, 0), ranks(n, 1);

        for (int i = 0; i < n; ++i) {
            parents[i] = i;
        }

        vector<t3i> edges; // {dist, u, v}

        // 總共有 O(n^2) 條邊
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                const int dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
                edges.emplace_back(t3i{dist, i, j});
            }
        }

        // 根據每條邊的 dist 由小到大做排序
        sort(edges.begin(), edges.end());

        int res = 0, cnt = 0;
        for (const auto& [dist, i, j] : edges) {
            const int r1 = find(parents, i); // root of i
            const int r2 = find(parents, j); // root of j

            // 若 i, j 不為同一個 set, 代表加入 edge 後不會形成 cycle
            if (r1 != r2) {
                cnt++;
                res += dist;
                union_(parents, ranks, r1, r2);
            }

            // 得到 n - 1 條邊就結束
            if (cnt == n - 1) {
                break;
            }
        }
        return res;
    }

private:
    int find(vector<int>& parents, int i){
        while (i != parents[i]) {
            parents[i] = parents[parents[i]]; // path compression
            i = parents[i];
        }
        return i;
    }

    void union_(vector<int>& parents, vector<int>& ranks, const int r1, const int r2){
        if (ranks[r1] > ranks[r2]) {
            parents[r2] = r1;
        } else if (ranks[r2] > ranks[r1]) {
            parents[r1] = r2;
        } else {
            parents[r2] = r1;
            ++ranks[r1];
        }
    }
};
  • time：$O(n^2 \cdot log(n))$ ➔ Dijkstra 演算法的時間複雜度為 $O(E \cdot log(E))$, 因為要對所有邊做排序, 而 E = $\binom{n}{2}$ = $O(n^2)$
  • space：$O(n^2)$ ➔ edges

Solution 2：

想法：利用 Prim 演算法

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        const int n = points.size();
        vector<bool> visited(n, false); // 紀錄哪些點在 MST 中
        vector<int> minDis(n, INT_MAX); // 尚未加入 MST 的點距離 MST 中的點之最小距離

        // 以 0 為起點 (任意點開始)
        minDis[0] = 0;

        int res = 0;
        for (int k = 0; k < n; ++k) { // 取 n 個點便結束
            int curMinEdge = INT_MAX;
            int cur = -1;

            // 取出 cost 最小的邊 (一開始會取 0 -> 0, 因為 minDis[0] = 0 < curMinEdge)
            for (int i = 0; i < n; ++i) {
                if (!visited[i] && minDis[i] < curMinEdge) {
                    curMinEdge = minDis[i];
                    cur = i;
                }
            }

            visited[cur] = true;
            res += curMinEdge;

            // 更新距離
            for (int i = 0; i < n; ++i) {
                if (!visited[i]) {
                    const int dist = abs(points[cur][0] - points[i][0]) + abs(points[cur][1] - points[i][1]);
                    minDis[i] = min(minDis[i], dist);
                }
            }
        }
        return res;
    }
};
  • time：$O(n^2)$ ➔ for loop
  • space：$O(n)$ ➔ visited, minDis