最小生成树：Prim 与 Kruskal 的实现差异与选型决策

最小生成树Prim 与 Kruskal 的实现差异与选型决策一、同是最小生成树为什么需要两种算法在刷 LeetCode 的图论题时第一次遇到最小生成树MST很多人会学到两种算法Prim 和 Kruskal。但如果你在面试中被问到为什么这道题选 Prim 不选 Kruskal你能答出多少大多数人的答案是Prim 用点扩展Kruskal 用边排序。这句话没错但它无法帮助你做工程决策。真正需要理解的是在什么场景下这两个算法的时间复杂度可以相差一个量级在什么场景下即使复杂度相同实际表现也截然不同最小生成树的核心问题定义是在无向带权连通图中找出一棵包含所有顶点的树使得边的权重之和最小。Prim 从一个起点出发每次选择与当前生成树相连的最小权重边逐步扩展。Kruskal 则按权重从小到大遍历所有边用并查集维护连通性每次选择不形成环的最小边。两个算法解决的是同一个问题但它们在思维方式、数据结构依赖和适用场景上完全不同。这篇文章将从底层机制出发把这两个算法的选择决策讲透。flowchart TB subgraph Prim算法 A[选择起点] -- B[维护优先队列: 候选边] B -- C[取出最小权重边] C -- D{边的终点是否已访问?} D --|否| E[加入 MST, 标记访问, 更新候选边] D --|是| C E -- F{MST 包含所有顶点?} F --|否| C F --|是| G[算法结束] end subgraph Kruskal算法 H[所有边按权重排序] -- I[取出最小权重边] I -- J{边的两端点是否连通?} J --|否| K[加入 MST, 合并集合] J --|是| I K -- L{MST 含 V-1 条边?} L --|否| I L --|是| M[算法结束] end二、并查集与优先队列两种底层数据结构的博弈Prim 算法需要一个优先队列通常是最小堆。每次从堆中取出权重最小的边如果边的终点尚未加入 MST 就将其加入并把该顶点的所有邻边放入堆中。由于每条边最多进入堆一次、弹出一次而堆操作是 O(log E)总时间 O(E log E)。在稠密图中 E ≈ V²时间复杂度退化为 O(E log V)与堆的实现相关。Kruskal 算法的瓶颈不是堆而是排序加并查集。边的排序需要 O(E log E)之后每条边做一次 Find 操作和至多 V-1 次 Union 操作。并查集在路径压缩和按秩合并下的均摊复杂度接近 O(α(V))其中 α 是反阿克曼函数几乎为常数。因此 Kruskal 的总时间由排序主导O(E log E)。这就揭示了选型的关键图类型Prim 复杂度Kruskal 复杂度推荐算法稠密图 (E ≈ V²)O(V²) 或 O(E log V)O(E log E) O(V² log V)Prim稀疏图 (E ≈ V)O(E log V)O(E log E) ≈ O(V log V)均可已排序边O(E log V)O(E α(V))Kruskal为什么在稠密图中 Prim 更好因为每条边在排序后都要遍历而 Kruskal 的排序开销无法避免。Prim 的堆操作虽然每条边都有开销但堆的大小上限是 V在稠密图中堆操作代价远小于排序。三、两种算法的完整实现与对比 Prim 算法 —— 基于最小堆的实现 适用场景稠密图邻接矩阵表示时效果更好 时间复杂度O(E log V) import heapq from typing import List, Tuple def prim_mst(n: int, edges: List[Tuple[int, int, int]]) - List[Tuple[int, int, int]]: n: 顶点数编号 0 到 n-1 edges: 边列表每条边为 (u, v, weight) 返回MST 中的边列表 为什么用邻接表Prim 需要快速获取某顶点的所有邻边 邻接表比邻接矩阵在稀疏图中有更好的空间效率。 # 构建邻接表 —— 每条边存 (邻居节点, 权重) graph [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w)) graph[v].append((u, w)) # 无向图双向添加 visited [False] * n mst_edges [] total_weight 0 # 最小堆存储格式(权重, 起点, 终点) # 为什么同时存起点终点构建 MST 时需要保留边的信息 pq [(0, -1, 0)] # (权重, 起点, 终点)从顶点 0 开始 while pq and len(mst_edges) n - 1: weight, from_node, to_node heapq.heappop(pq) # 跳过已访问节点的边避免形成环 if visited[to_node]: continue visited[to_node] True if from_node ! -1: mst_edges.append((from_node, to_node, weight)) total_weight weight # 将新加入顶点的所有邻边入堆 # 为什么即使边会重复入堆也不处理 # visited 数组保证了只有最小的边会被选中 for neighbor, w in graph[to_node]: if not visited[neighbor]: heapq.heappush(pq, (w, to_node, neighbor)) return mst_edges Kruskal 算法 —— 基于并查集的实现 适用场景稀疏图边已预排序时效率极高 时间复杂度O(E log E)主要由排序决定 class UnionFind: 带路径压缩和按秩合并的并查集 def __init__(self, n: int): self.parent list(range(n)) self.rank [0] * n # 按秩合并秩不是高度是上界 def find(self, x: int) - int: # 路径压缩将查找路径上的所有节点直接挂在根上 # 这样做让后续查找接近 O(1) if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x: int, y: int) - bool: 返回 True 表示合并成功False 表示已在同一集合 rx, ry self.find(x), self.find(y) if rx ry: return False # 按秩合并将秩小的树挂在秩大的树下 # 为什么这样设计防止树退化成链表保证 find 的均摊效率 if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 return True def kruskal_mst(n: int, edges: List[Tuple[int, int, int]]) - List[Tuple[int, int, int]]: n: 顶点数 edges: 边列表 (u, v, weight) 返回MST 中的边列表 uf UnionFind(n) mst_edges [] total_weight 0 # 按权重排序Kruskal 的核心排序决定整体复杂度 sorted_edges sorted(edges, keylambda e: e[2]) for u, v, w in sorted_edges: if uf.union(u, v): mst_edges.append((u, v, w)) total_weight w # MST 共有 n-1 条边提前退出 if len(mst_edges) n - 1: break return mst_edges四、工程场景下的选型边界场景一网络布线问题稠密图。需要连接大量节点任意两点间都有一条带权边。Prim 天然适合因为邻接矩阵下可以直接用 O(V²) 的朴素实现比堆优化版更简洁。场景二地图路径规划稀疏图。路网是典型的稀疏图每个路口只连接几条路。此时 Kruskal 更有优势因为边数少排序代价低且并查集操作极快。场景三边已经按权重排序。比如从外部服务获取的数据已经是排好序的。Kruskal 可以直接使用省去排序的 O(E log E)总时间接近 O(E α(V))。场景四动态加边。如果图在运行时不断新增边Kruskal 每次都要重新排序或维护有序集合。而 Prim 可以在当前 MST 基础上增量计算更灵活。一个重要的工程细节Kruskal 可以通过并查集天然支持已存在的部分 MST。如果有几条边已经被预先确定要加入 MST只需在初始化并查集时提前 union 对应的节点即可。Prim 要做到这一点需要额外的处理。五、总结Prim 和 Kruskal 在数学上是等价的工程上却各有优劣。选型的决定性因素有三个图的稀疏度决定复杂度主导项、数据表示形式邻接矩阵还是边列表、以及是否需要增量计算。但更重要的是对底层数据结构的理解。Prim 的效率依赖堆的性质——堆的插入和删除决定了它的实际表现。Kruskal 的效率依赖并查集的平摊分析——路径压缩和按秩合并缺一不可。如果面试时你不仅能写出这两种算法的代码还能解释为什么会这样选择那面试官会看到一个超越刷题模板的候选人。