连接所有点的最小费用

枚举所有连接方式是指数级。

Prim 每次从已连通集合向外选最便宜的边，直到所有点接入。

① MST：用最小总费用把所有点连成一片：最小生成树(MST)：选若干条边把 5 个点连通、总费用最小。两点费用 ＝ 曼哈顿距离 |Δx|+|Δy|。Prim 从任一点出发，每次贪心接一条「连向新点的最短边」。

② 从 P0 出发，选最短边 P0–P1 ＝ 4：起点 P0，它到各点：P1=4、P3=7、P4=7、P2=13。选最短的 P0–P1=4，把 P1 连进来。

③ 边界最短 P1–P3 ＝ 3 → 接入 P3：已连 {P0,P1}。跨越「已连/未连」的最短边是 P1–P3=3 → 接入 P3，累计 7。

④ P3–P4 ＝ 4 最短 → 接入 P4：已连 {P0,P1,P3}。最短跨越边 P3–P4=4 → 接入 P4，累计 11。

⑤ 最后接 P2：P1–P2 ＝ 9 最短 → 总费用 20：只剩 P2，到它最短的是 P1–P2=9（比 P3–P2=10、P0–P2=13、P4–P2=14 都小）→ 接入。5 点全连通，总费用 ＝ 20。

一句话记住：Prim 每次从已连通集合向外选最便宜的边，直到所有点接入。

边界三连：本题真边界：单点、两点、共线。

⑥ 为什么贪心选「最短跨越边」对？(切分定理)：切分定理：把点分成「已连」「未连」两堆，跨越两堆的那条最短边一定属于某棵 MST——所以每次贪心接最短跨越边不会错。注意这是完全图(任意两点都有边)，边数 O(n²)，用堆的 Prim 复杂度 O(n² log n)。

面试追问 · 核心思路：思路：完全图上跑 Prim，最小堆每次接最短跨越边。

面试追问 · Prim vs Kruskal：稠密图(完全图)选 Prim；稀疏图 Kruskal+并查集更优。

面试追问 · 复杂度：复杂度：懒惰 Prim O(n² log n)；稠密 Prim 可到 O(n²)。

这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问“Prim 为什么每步接最短边就最优”。