连接所有点的最小费用
这题本质上不是最短路径，而是最小生成树：我们关心的是把所有点连成一张网的总代价最小，而不是某两点之间的距离最短。
问题描述
LeetCode 1584 - 连接所有点的最小费用
给定一个数组points，其中points[i] = [xi, yi]表示平面上的一个点。连接两点的费用为它们之间的曼哈顿距离。返回连接所有点的最小费用。
输入: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出: 20
说明:
连接方式: (0,0)-(2,2)-(5,2)-(7,0)-(3,10)
费用: 4 + 3 + 2 + 11 = 20
解题思路
- 最小生成树：将点看作节点，距离看作边权
- Prim算法：从点扩展
- Kruskal算法：从边扩展
- 曼哈顿距离：|x1-x2| + |y1-y2|
为什么这题不是最短路径
最短路径关心的是：
起点到终点最短而这题关心的是：
所有点都连起来，总花费最小这是最小生成树的标准定义，所以优先应该往 Prim / Kruskal 想。
Go 代码
Go 实现
import (
"container/heap"
)
type Edge struct {
cost, u, v int
}
type PQ []Edge
func (pq PQ) Len() int { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].cost < pq[j].cost }
func (pq PQ) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x interface{}) { *pq = append(*pq, x.(Edge)) }
func (pq *PQ) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
func minCostConnectPoints(points [][]int) int {
n := len(points)
if n <= 1 {
return 0
}
manhattanDistance := func(p1, p2 []int) int {
return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
}
visited := make(map[int]bool)
visited[0] = true
totalCost := 0
pq := &PQ{}
heap.Init(pq)
for i := 1; i < n; i++ {
dist := manhattanDistance(points[0], points[i])
heap.Push(pq, Edge{dist, 0, i})
}
for pq.Len() > 0 && len(visited) < n {
edge := heap.Pop(pq).(Edge)
if visited[edge.v] {
continue
}
visited[edge.v] = true
totalCost += edge.cost
for i := 0; i < n; i++ {
if !visited[i] {
dist := manhattanDistance(points[edge.v], points[i])
heap.Push(pq, Edge{dist, edge.v, i})
}
}
}
return totalCost
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}易错点
这题最容易错的是把“边数很多”这件事想得太重，反而忘了最核心的 MST 结构。
- 曼哈顿距离是边权，不是坐标差单独比较。
- Prim 是“从已选点集向外扩展”，Kruskal 是“从小边开始选”。
- 完全图场景下边很多，代码实现通常更偏向 Prim。
- 不要把“连接所有点”误写成多源最短路。
复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| Prim | O(N² log N) | O(N²) |
| Kruskal | O(N² log N) | O(N²) |