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

约 6 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 图森
标签
数组 图 并查集 最小生成树

题目描述

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

image-20260929085320773

image-20260929085320880

image-20260929085320987

题意分析

平面上任意两点都可以直接连接，费用为曼哈顿距离，即横坐标差的绝对值加纵坐标差的绝对值。要求所有点连通，且任意两点之间只有一条简单路径，因此选出的连接应当构成一棵生成树。

目标是让全部连接边的费用总和最小，不是让某个起点到其他点的路径分别最短。可以用 Prim 算法，从一个点开始逐步扩展已连接的集合。

解法：Prim 最小生成树

核心思路

[!blue]

用 inMst[v] 标记点是否已经加入生成树，minDist[v] 表示未加入点 v 到已选点集合的最小单边费用。每轮在所有未加入点中选 minDist 最小的 u，相当于选择当前跨越“已选、未选”两部分的最便宜连接。

这条边可以安全加入最优解。考虑一棵包含此前已选边的最优生成树：如果它没有当前最小跨界边，加入这条边会形成一个环，环上必然还有另一条跨越同一边界的边。后者的费用不会更小，用当前边替换它仍然连通且费用不增加。因此每次贪心选择后，仍存在包含全部已选边的最优生成树。

加入 u 后，对每个未加入点 v，用 u 到 v 的曼哈顿距离更新 minDist[v]。旧值已经涵盖此前所有已选点，现在只需检查新点提供的连接，始终保留到整个集合最便宜的一条边。

所有点之间都有边，但不必保存完整图，更新时按坐标计算距离即可。任意点都可作为起点，代码把第 0 个点的候选费用设为 0；执行 n 轮加入全部点，只有后面的 n - 1 轮计入真实边的费用。

解题步骤

  1. 将所有点标为未加入，候选距离设为足够大的值，仅起点距离设为 0。
  2. 扫描未加入点，选择 minDist 最小的点 u。
  3. 标记 u 已加入，并将它的候选费用累加到答案。
  4. 遍历其余未加入点，计算与 u 的曼哈顿距离，若更便宜则更新候选值。
  5. 重复 n 轮后返回总费用。只有一个点时，唯一一轮加入费用为 0。

代码实现

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        // 记录到已选集合的最小单边费用，不是从起点出发的路径距离。
        int[] minDist = new int[n];
        boolean[] inMst = new boolean[n];
        int inf = Integer.MAX_VALUE / 4;

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

        // 起点零费用加入，后续轮次才计入真实连接边。
        minDist[0] = 0;

        int answer = 0;

        for (int i = 0; i < n; i++) {
            // 在全部未加入点中选择最便宜的连接。
            int u = -1;

            for (int j = 0; j < n; j++) {
                if (!inMst[j] && (u == -1 || minDist[j] < minDist[u])) {
                    u = j;
                }
            }

            inMst[u] = true;
            answer += minDist[u];

            for (int v = 0; v < n; v++) {
                if (inMst[v]) {
                    continue;
                }

                int d =
                        Math.abs(points[u][0] - points[v][0])
                                + Math.abs(points[u][1] - points[v][1]);

                // 新点提供更便宜的直接连接时，更新候选费用。
                if (d < minDist[v]) {
                    minDist[v] = d;
                }
            }
        }

        return answer;
    }
}

func minCostConnectPoints(points [][]int) int {
    n := len(points)
    inf := int(^uint(0) >> 1)
    // 记录到已选集合的最小单边费用，不是从起点出发的路径距离。
    minDist := make([]int, n)
    inMst := make([]bool, n)
    for i := 0; i < n; i++ {
        minDist[i] = inf / 4
    }
    // 起点零费用加入，后续轮次才计入真实连接边。
    minDist[0] = 0

    answer := 0
    for i := 0; i < n; i++ {
        // 在全部未加入点中选择最便宜的连接。
        u := -1
        for j := 0; j < n; j++ {
            if inMst[j] {
                continue
            }
            if u == -1 || minDist[j] < minDist[u] {
                u = j
            }
        }
        inMst[u] = true
        answer += minDist[u]

        for v := 0; v < n; v++ {
            if inMst[v] {
                continue
            }
            dx := points[u][0] - points[v][0]
            if dx < 0 {
                dx = -dx
            }
            dy := points[u][1] - points[v][1]
            if dy < 0 {
                dy = -dy
            }
            d := dx + dy
            // 新点提供更便宜的直接连接时，更新候选费用。
            if d < minDist[v] {
                minDist[v] = d
            }
        }
    }

    return answer
}

复杂度分析

  • 时间复杂度：$O(n²)$，每轮选择和更新均扫描全部点。
  • 空间复杂度：$O(n)$，保存加入标记和候选距离。

关键点总结

[!green]

  • minDist 保存连接已选集合的一条边，不是从起点出发的累计路径距离。
  • 每轮选择所有跨界连接中最小的一条，替换论证保证这一步不会破坏最优性。
  • 每次加入一个未选点，所以不会形成环；加入全部点后恰好得到生成树。
  • 完全图的边权按需计算，避免存储平方数量的边。

易错点总结

[!yellow]

  • 更新候选时不要加上 minDist[u]，那是最短路径算法的转移方式，不是本题需要的单边连接费用。
  • 不能只根据最后加入的点直接决定下一点，集合中更早加入的点仍可能提供更便宜的连接。
  • 总共要执行 n 轮加入操作；第一轮只是零费用起点，少一轮就会漏掉一个点。
  • 更新和选点都只针对尚未加入的点，已确定的树边不能重复计费。

相似题目

题目 难度 关联与区别
1135. 最低成本连通所有城市 中等 最小生成树目标相同，本题完整图的边权由点坐标的曼哈顿距离隐式给出。
1168. 水资源分配优化 困难 同样求最低全连通成本，原题额外用虚拟节点表示建井选择。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/85697259
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！