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

### 解决方案概述 对于LeetCode 1584题——连接所有点的最小费用，目标是在给定平面上的一组点之间建立边，使得这些点全部连通，并且总成本最低。此问题可以通过构建最小生成树(Minimum Spanning Tree, MST)[^2]来解决。 #### Prim's Algorithm 实现方法 Prim’s算法是一种用于求解无向图中最小生成树的有效贪心算法。该算法通过逐步扩展已有的部分生成树直到覆盖所有的顶点为止，在每一步都选择当前未加入的部分中最短的边。 ```python import heapq def minCostConnectPoints(points): n = len(points) # 计算曼哈顿距离作为权重函数 def manhattan(p1, p2): return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1]) visited = set() heap = [(0, 0)] # (cost, point_index) result = 0 while len(visited) < n: cost, i = heapq.heappop(heap) if i in visited: continue visited.add(i) result += cost for j in range(n): if j not in visited and j != i: heapq.heappush(heap, (manhattan(points[i], points[j]), j)) return result ``` 上述代码实现了基于优先队列优化版本的Prim’s算法。首先定义了一个辅助函数`manhattan()`用来计算两点之间的曼哈顿距离；接着初始化一个小根堆存储候选节点及其对应的代价；最后进入循环直至访问过所有节点并累加路径长度得到最终的结果。 #### Kruskal's Algorithm 实现方式 Kruskal’s算法也是一种常用的MST算法，它按照从小到大的顺序处理各条边，只当一条边不会形成环路时才将其添加至正在形成的森林里。为了高效实现这一点，可以采用Union-Find数据结构来进行动态集合操作。 ```python class UnionFind(object): def __init__(self, size): self.parent = list(range(size)) def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, u, v): rootU = self.find(u) rootV = self.find(v) if rootU == rootV: return False else: self.parent[rootU] = rootV return True def minCostConnectPoints_kruskal(points): edges = [] n = len(points) for i in range(n): for j in range(i+1, n): distance = abs(points[i][0] - points[j][0]) + \ abs(points[i][1] - points[j][1]) edges.append((distance, i, j)) uf = UnionFind(n) edges.sort() res = 0 count = 0 for dist, u, v in edges: if uf.union(u, v): res += dist count += 1 if count >= n-1: break return res ``` 这段Python程序展示了如何利用Kruskal的方法解决问题。创建了名为`edges`列表保存所有可能存在的边以及它们各自的权值（即两个端点间的曼哈特尼距离），之后对其进行升序排列。随后遍历排序后的边集尝试将符合条件的新边纳入结果集中去，同时维护一个计数器确保恰好选择了\(n−1\)条独立边构成一棵完整的树形结构。