LeetCode 1584中等高级图
连接所有点的最小费用 图解题解
这道题到底在问什么
用曼哈顿距离作为边权，连接所有点且总费用最小。
- 示例
- points=[[0,0],[2,2],[3,10],[5,2],[7,0]] → 20
先想最直接的笨办法
枚举所有连接方式是指数级。（动画第 3 步）
最优解：一步一步想明白
- 3枚举所有连接方式是指数级。
- 4Prim 每次从已连通集合向外选最便宜的边，直到所有点接入。
- 5最小生成树(MST)：选若干条边把 5 个点连通、总费用最小。两点费用 ＝ 曼哈顿距离 |Δx|+|Δy|。Prim 从任一点出发，每次贪心接一条「连向新点的最短边」。
- 6起点 P0，它到各点：P1=4、P3=7、P4=7、P2=13。选最短的 P0–P1=4，把 P1 连进来。
- 7已连 {P0,P1}。跨越「已连/未连」的最短边是 P1–P3=3 → 接入 P3，累计 7。
- 8已连 {P0,P1,P3}。最短跨越边 P3–P4=4 → 接入 P4，累计 11。
- 9只剩 P2，到它最短的是 P1–P2=9（比 P3–P2=10、P0–P2=13、P4–P2=14 都小）→ 接入。5 点全连通，总费用 ＝ 20。
- 12一句话记住：Prim 每次从已连通集合向外选最便宜的边，直到所有点接入。
- 15切分定理：把点分成「已连」「未连」两堆，跨越两堆的那条最短边一定属于某棵 MST——所以每次贪心接最短跨越边不会错。注意这是完全图(任意两点都有边)，边数 O(n²)，用堆的 Prim 复杂度 O(n² log n)。
- 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问“Prim 为什么每步接最短边就最优”。
⚠️ 容易写错的地方
✗ 错：把它当稀疏图、只连"看起来近"的点
✓ 对：这是完全图：任意两点都有边(曼哈顿距离)
MST 必须在所有 n²/2 条潜在边里选，漏边会错过更优连接。
✗ 错：弹出堆顶不判 seen 就累加
✓ 对：弹出后若该点已连入则跳过(懒惰删除)
同一点会以不同费用多次入堆，只认第一次(最小)弹出，否则重复计费。
✗ 错：费用用欧氏距离 / 直线距离
✓ 对：用曼哈顿距离 |Δx|+|Δy|
题目定义费用就是曼哈顿距离，算错距离整棵树都错。
完整代码（Python / C++ / Java）
Python
class Solution:
def minCostConnectPoints(self, points):
import heapq
n = len(points)
seen = set()
heap = [(0, 0)]
ans = 0
while len(seen) < n:
cost, i = heapq.heappop(heap)
if i in seen:
continue
seen.add(i)
ans += cost
x1, y1 = points[i]
for j, (x2, y2) in enumerate(points):
if j not in seen:
heapq.heappush(heap, (abs(x1 - x2) + abs(y1 - y2), j))
return ansC++
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size(), ans = 0;
vector<int> seen(n);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0,0});
int used = 0;
while (used < n) {
auto [cost, i] = pq.top(); pq.pop();
if (seen[i]) continue;
seen[i] = 1; used++; ans += cost;
for (int j=0;j<n;j++) if (!seen[j]) {
int w = abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1]);
pq.push({w,j});
}
}
return ans;
}
};Java
class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length, used = 0, ans = 0;
boolean[] seen = new boolean[n];
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0,0});
while (used < n) {
int[] cur = pq.poll();
int cost = cur[0], i = cur[1];
if (seen[i]) continue;
seen[i] = true; used++; ans += cost;
for (int j=0;j<n;j++) if (!seen[j]) {
int w = Math.abs(points[i][0]-points[j][0]) + Math.abs(points[i][1]-points[j][1]);
pq.offer(new int[]{w,j});
}
}
return ans;
}
}套路模板 · 完全图 Prim 骨架
# 完全图 Prim（最小生成树）骨架
seen = set(); heap = [(0, 0)]; ans = 0
while len(seen) < n:
cost, i = heappop(heap)
if i in seen: continue # 懒惰删除：已连入则跳过
seen.add(i); ans += cost
for j in range(n):
if j not in seen: # 向所有未连点扩边
heappush(heap, (曼哈顿(i, j), j))
return ans复杂度
时间复杂度
O(n² log n)
完全图 n² 条边，懒惰 Prim 每条入堆 O(log n)
空间复杂度
O(n²)
堆里最多堆积 O(n²) 条候选边（懒惰删除）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 连接所有点的最小费用 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
整体思路是什么？+
把点两两连边(费用=曼哈顿距离)得到完全图，在上面求最小生成树。用 Prim：从 P0 出发，最小堆里放「已连点到各未连点」的边，每次弹出最短的、若目标点未连入就接上并累加费用，直到所有点连通。
这道题为什么用「高级图」，换最直接的暴力解会差在哪？+
高级图抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。