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

发布时间：2026/7/12 21:49:23

最小生成树：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, key=lambda 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