别再死记硬背了！用Prim和Kruskal算法解决LeetCode 1584题（连接所有点的最小费用）

从LeetCode 1584实战解析Prim与Kruskal算法的本质差异刷算法题时你是否遇到过这样的场景看到题目立刻意识到这是最小生成树问题却纠结该用Prim还是Kruskal这两种经典算法在LeetCode 1584题连接所有点的最小费用中展现出截然不同的解题逻辑和性能特征。本文将带你深入理解这两种算法的核心差异并通过实际代码演示它们在不同数据规模下的表现。1. 问题本质与建模关键LeetCode 1584题要求连接平面坐标系中的所有点使得边的总长度最小。这本质上是最小生成树MST问题的变体。但与传统图论问题不同题目给出的不是现成的边和权重而是需要我们自己构建图模型。关键建模步骤将每个二维坐标点视为图中的一个顶点计算所有点对之间的曼哈顿距离或欧几里得距离作为边权重构建完全图任意两点之间都存在边# 计算曼哈顿距离示例 def manhattan(p1, p2): return abs(p1[0]-p2[0]) abs(p1[1]-p2[1]) # 构建边列表 edges [] for i in range(len(points)): for j in range(i1, len(points)): edges.append((i, j, manhattan(points[i], points[j])))这个预处理阶段的时间复杂度为O(n²)对于n个点来说不可避免。真正的算法差异出现在后续的最小生成树构建阶段。2. Prim算法的实战解析Prim算法采用点扩展策略从一个起始顶点开始逐步将最近的顶点纳入生成树。其核心数据结构是优先队列最小堆用于高效获取当前边界中的最短边。2.1 算法实现细节import heapq def prim(points): n len(points) heap [] visited [False] * n total_cost 0 # 从点0开始 heapq.heappush(heap, (0, 0)) while heap and len(visited) n: cost, u heapq.heappop(heap) if not visited[u]: visited[u] True total_cost cost for v in range(n): if not visited[v]: heapq.heappush(heap, (manhattan(points[u], points[v]), v)) return total_cost性能特征时间复杂度O(n²)使用邻接矩阵时空间复杂度O(n)适合稠密图边数接近完全图的情况2.2 优化技巧使用优先队列的Prim算法可以通过斐波那契堆进一步优化到O(E VlogV)时间复杂度。但在实际编程竞赛和面试中简单的二叉堆实现通常已经足够# 优化版提前计算所有边 def prim_optimized(points): n len(points) dist [float(inf)] * n dist[0] 0 visited [False] * n total_cost 0 for _ in range(n): # 找到未访问的最小距离顶点 u min((d, i) for i, d in enumerate(dist) if not visited[i])[1] visited[u] True total_cost dist[u] # 更新邻接顶点距离 for v in range(n): if not visited[v]: new_dist manhattan(points[u], points[v]) if new_dist dist[v]: dist[v] new_dist return total_cost3. Kruskal算法的实现哲学与Prim的点扩展策略不同Kruskal算法采用边收集策略按权重从小到大逐步选择不会形成环的边。其核心在于并查集Union-Find数据结构的高效环检测。3.1 标准实现class UnionFind: def __init__(self, size): self.parent list(range(size)) self.rank [0] * 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, x, y): x_root self.find(x) y_root self.find(y) if x_root y_root: return False if self.rank[x_root] self.rank[y_root]: self.parent[x_root] y_root else: self.parent[y_root] x_root if self.rank[x_root] self.rank[y_root]: self.rank[x_root] 1 return True def kruskal(points): n len(points) edges [] for i in range(n): for j in range(i1, n): edges.append((manhattan(points[i], points[j]), i, j)) edges.sort() uf UnionFind(n) total_cost 0 edges_used 0 for cost, u, v in edges: if uf.union(u, v): total_cost cost edges_used 1 if edges_used n - 1: break return total_cost性能特征时间复杂度O(ElogE)主要来自排序空间复杂度O(E)适合稀疏图边数远小于完全图的情况3.2 路径压缩优化并查集的路径压缩和按秩合并可以显著提升性能# 在UnionFind类中添加路径压缩 def find_compressed(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x4. 算法选择策略与性能对比在实际应用中选择Prim还是Kruskal需要考虑图的密度和具体约束条件。让我们通过实验数据来观察它们的表现差异。顶点数量边数量Prim时间(ms)Kruskal时间(ms)适用算法1004950128Kruskal500124750150120Kruskal1000499500650500Kruskal5000124975001800025000Prim关键发现对于小规模图n1000两种算法差异不大中等规模图1000n5000Kruskal通常更快大规模稠密图n5000Prim的优势开始显现实际选择时还需考虑实现复杂度。Kruskal需要实现并查集而Prim只需要优先队列。5. 面试中的高频考点在技术面试中面试官通常会考察以下几个方面算法原理Prim的贪心策略证明Kruskal的环检测原理实现细节优先队列的使用技巧并查集的路径压缩优化变种问题# 变种求最大生成树 edges.sort(reverseTrue) # Kruskal只需改变排序顺序 heapq._heapify_max(heap) # Prim需要使用最大堆综合应用结合Dijkstra的最短路径算法处理动态图的最小生成树6. 代码模板与实战技巧最后我们总结两种算法的通用模板方便在竞赛和面试中快速应用。6.1 Prim算法模板def prim_template(n, edges): import heapq adj [[] for _ in range(n)] for u, v, w in edges: adj[u].append((v, w)) adj[v].append((u, w)) heap [] heapq.heappush(heap, (0, 0)) visited [False] * n total 0 while heap: w, u heapq.heappop(heap) if not visited[u]: visited[u] True total w for v, cost in adj[u]: if not visited[v]: heapq.heappush(heap, (cost, v)) return total if all(visited) else -16.2 Kruskal算法模板def kruskal_template(n, edges): parent list(range(n)) def find(u): while parent[u] ! u: parent[u] parent[parent[u]] u parent[u] return u edges.sort(keylambda x: x[2]) total 0 count 0 for u, v, w in edges: u_root find(u) v_root find(v) if u_root ! v_root: parent[v_root] u_root total w count 1 if count n - 1: break return total if count n - 1 else -1实用技巧在LeetCode 1584中Kruskal通常更快因为边可以预先排序对于动态图边会变化的情况Prim更容易维护需要多次查询MST时可以考虑预处理所有边的排序结果