★ FEATURED ARTICLE 如果你在大学里学过数据结构这门课里最容易被低估的内容之一我猜是最小生成树。它的场景很直白给一张连通的无向带权图要在 n 个点之间选出 n-1 条边把所有点连在一起同时让这些边的总权重最小。这个问题的两个经典解法就是 Prim 算法和 Kruskal 算法。我当时第一次看到它们的时候觉得不过就是两套贪心规则而已后来真正去手算、写代码、跑几个测试用例才发现里面值得掰开揉碎讲的细节其实不少。很多教材会把这两个算法放在同一节里好像讲完就结束了。但实际上它们一个是“从一个点慢慢长大成一棵树”另一个是“把一堆碎片逐步拼成一棵树”思考路径完全不同。你如果不搞清楚它们背后的依据做题的时候会陷入一个很尴尬的状态能默写下伪代码但一变图就不知道错在哪。这篇文章我打算把算法背后的贪心依据、两种算法的完整过程、代码实现细节还有我实际调试时踩过的坑一次性说清楚。1. 先把问题本身看透最小生成树到底在求什么1.1 从一个小场景引出图的模型想象一下现在有 6 个城市要通网络已知任意两个城市之间拉光缆的造价怎么选线路让总造价最低这个问题抽象成图就是顶点是城市边是可能的线路边权是造价。我们最后要留下的不是一个包含所有边的图而是一个能连通所有顶点且总权重最小的边集。为什么结果一定是一棵树因为只要加了 n-1 条边就能连通 n 个顶点。如果你选了 n 条边多出来的那一条必定会形成环从环里删掉任意一条边图依然是连通的但总权重只会变小或不变。所以最终答案不可能是“带环的连通图”只能是一棵树。这就是最小生成树这个名字的来源一颗“连接全部顶点、总权重最小”的树。这里有一个容易混淆的点图本身可能带环但我们选的边不能带环。Prim 和 Kruskal 每一步真正在做的事情就是“在安全的前提下把一条边加入答案”。所谓安全指加入后不会成环且这条边必然存在于某棵最小生成树中。理解了“安全边”这个概念再去读两种算法的步骤会顺畅很多。1.2 贪心策略凭什么正确割定理很多初学者会问每一步都选当前看起来最小的边最后结果能保证全局最优吗这在图论里不是一个“感觉对就行”的问题它有一个非常漂亮的支撑原理一般叫割定理或者 cut property。先把图中的所有顶点分成两组比如左边一组 A右边一组 B。这种分组方式就叫一个“割”而两端分别落在两组里的边叫“跨越这个割的边”。割定理说的是在跨越某个割的所有边里权重最小的那条边一定存在于某棵最小生成树中。证明思路不复杂。假设这条最小跨越边是 e而某棵最小生成树 T 里没有 e。把 e 加入 TT 里必然出现一个环。这个环要连通左右两组因此环里一定还有另一条跨越割的边 e。把 e 从环里删掉把 e 放回去图依然是连通的而且总权重不会变大。所以必然存在一棵包含 e 的最小生成树。Prim 算法做的就是始终把当前生成树看成 A 组剩下的顶点看成 B 组每次选跨越这两组的最小边。Kruskal 做的则是每时每刻都有多个等价类每个等价类是一组某条边如果连接两个不同的组这条边就在“这两个组形成的割”里是最小的跨越边之一。两个算法都不过是在反复使用割定理而已。2. Prim 算法像水波纹一样从一点向外扩2.1 算法步骤拆解Prim 算法的思路很容易记住随便选一个起点把它当成一棵只有一个节点的树然后每次找一条“一端在这棵树里、另一端不在树里”的边选权重最小的把新的顶点加进树里重复直到所有顶点都进来。伪代码可以写成这样visited[1] true while 生成树里的顶点数 n: 从所有 (u, v, w) 中找满足 u 已访问、v 未访问的最小 w 对应的边 visited[v] true ans w 更新所有从 v 出发、指向未访问顶点的边注意它和 Dijkstra 长得非常像但含义完全不同。Dijkstra 维护的是“从起点到各个点的最短距离”更新时是dist[v] min(dist[v], dist[u] w)Prim 维护的是“生成树边界到各个外部点的最短连接边”更新时是key[v] min(key[v], w)不加前缀距离。如果你按 Dijkstra 的写法把距离累加起来结果必错。2.2 手算一个完整例子光看伪代码不够我实际算一遍给你看。考虑下面这个 6 个顶点的图顶点编号 1 到 6边和权重如下(1,2)6(1,3)1(1,4)5(2,3)5(2,5)3(3,4)5(3,6)4(4,6)2(5,6)6从顶点 1 开始每一轮选边如下轮次当前树内顶点连接树内与树外的候选边本轮选中的边1{1}(1,2)6, (1,3)1, (1,4)5(1,3)12{1,3}(1,2)6, (1,4)5, (3,2)5, (3,4)5, (3,6)4(3,6)43{1,3,6}(1,2)6, (1,4)5, (3,2)5, (3,4)5, (6,4)2, (6,5)6(6,4)24{1,3,4,6}(1,2)6, (3,2)5, (6,5)6(3,2)55{1,3,4,6,2}(2,5)3, (6,5)6(2,5)3最终选出的边是(1,3)、(3,6)、(6,4)、(3,2)、(2,5)总权重 1425315。这个结果是不是唯一的最小生成树在这里刚好是 15但如果有同权边可能会有多个不同的最小生成树总数相同。这不影响算法正确性你随便选哪条合法最小边都行。为什么起点选哪个都无所谓因为初始时“割”就是 {起点} 和其余顶点Prim 选的是这个割的最小跨越边。下一步生成树集合扩大后又是新的一组割。每一步都符合割定理所以起点只是改变选边顺序不会改变最终最优总权重。2.3 两种实现姿势邻接矩阵和优先队列Prim 有两种常见实现方式。当图比较稠密比如 n 只有几百、上千边数接近 n²可以直接用邻接矩阵和 O(n²) 的扫描法。每次找一个未访问顶点中 key 最小的点然后更新邻接矩阵里的边。当图比较稀疏比如 n 很大但每条边都很少再用 O(n²) 扫描就会很亏这时应该用邻接表加优先队列。实现时有几个容易出错的点优先队列里可能同时存在同一个点的多个旧记录因为一条边可能被重复 push 多次。堆顶弹出的点如果已经访问过要直接跳过不能把这个权重累加到答案里。只有在visited[v] false时才需要把邻居边 push 进堆。复杂度上邻接矩阵版是 O(n²)优先队列版是 O(E log V)其中 E 是边数。实际刷题时题目给的图是稠密还是稀疏基本上决定了你该写哪种。3. Kruskal 算法把边从小到大一条条捡起来3.1 先把所有边排序再决定要不要Kruskal 的思路比 Prim 更“暴力”把图中所有边按权重从小到大排序然后从最小的开始一条条尝试加入答案。加入的唯一条件是这条边的两个端点当前不在同一个连通分量里如果在同一个分量里说明加进去会成环直接丢掉。所以整个算法的骨架特别简单把 edges 按权重从小到大排序 初始化并查集 ans 0 for (u, v, w) in edges: if find(u) ! find(v): union(u, v) ans w 如果已经选了 n-1 条边提前结束还是用刚才那张图。所有边排序后是(1,3)1, (4,6)2, (2,5)3, (3,6)4, (1,4)5, (2,3)5, (3,4)5, (1,2)6, (5,6)6。逐条处理当前边两个端点所在分量是否加入当前生成森林(1,3)1不同加入{1,3}(4,6)2不同加入{4,6}(2,5)3不同加入{2,5}(3,6)4连通 {1,3} 和 {4,6}加入{1,3,6,4} 和 {2,5}(1,4)51 和 4 已在同一分量跳过不变(2,3)5{2,5} 和 {1,3,6,4}加入全部连通最后选中的边是 (1,3)、(4,6)、(2,5)、(3,6)、(2,3)总权重也是 15。可以看到Kruskal 和前面对 Prim 手算选出的边并不完全一样但总权重一致。这也是最小生成树“结果可能不唯一”的一个具体体现。3.2 并查集优化Kruskal 的核心支柱Kruskal 如果不配合并查集每处理一条边都去遍历当前森林判断连通性复杂度会非常高。并查集要解决的核心问题是动态维护若干个不相交集合支持查询两个元素是否同属一个集合以及合并两个集合。标准做法有两个优化路径压缩和按秩合并。路径压缩让 find 过程中一路把节点直接挂到根上按秩合并则用集合大小或树高决定谁挂到谁下面避免并查集退化成一条长链。二者配合后每次 find/union 的均摊代价几乎可以看成常数也就是常说的反阿克曼函数量级。在普通竞赛题和面试题里你写一个带路径压缩和按 size 合并的并查集就足够了。另外注意一个细节算法不需要一开始就把边权相同的边分个先后。如果两条边权重一样先处理哪条都行最终总权重一样。前提是并查集逻辑正确并且真的按权重非降序处理。3.3 图不连通时怎么办最小生成树的前提是图连通。如果图本身是断开的Kruskal 处理完所有边后选中的边数一定小于 n-1。这时应该返回“不存在最小生成树”或者返回 -1。很多人第一次写这题时会漏掉这个判断直接在循环里 break最后输出 0这就会在断开图上出大问题。Prim 也一样。优先队列版本里如果堆空了但cnt n-1说明从起点出发根本连不全所有顶点应当返回不存在。邻接矩阵版本里如果某一轮找不到 key 值有限的未访问点同样说明图不连通。4. 两个算法放在一起对比才知道什么时候选谁4.1 核心差异对比对比维度Prim 算法Kruskal 算法建树思路从一个点逐渐扩张成一棵树从多条边逐渐合并成一片森林维护的数据结构visited 标记 优先队列/距离数组并查集是否需要全局排序不需要只关心当前边界最小边必须按边权从小到大排序天然适合的图稠密图稀疏图典型复杂度O(n²)或 O(E log V)O(E log E)额外空间邻接表/邻接矩阵存边数组实现核心难点更新边界 key 值时别写成距离累加find/union 别写错光看复杂度Prim 用堆是 O(E log V)Kruskal 是 O(E log E)。当 E 很大时Kruskal 的排序开销会凸显出来当图很稠密、E 接近 V² 时Prim 的邻接矩阵版 O(V²) 常常比 Kruskal 更稳。4.2 稠密图和稀疏图的选择逻辑实际做题或者写工程代码时我不会只看最坏复杂度还会看实现难度和常数。如果 n 范围是 1000 以内并且题目直接用邻接矩阵给你那写 Prim 矩阵版是最省心的循环两遍就完事。如果 n 是 10⁵边是 10⁶ 级别的稀疏图肯定用 Kruskal因为只需要一个边数组和一个并查集内存可控。还有一种情况题目给的边已经排好序那几乎不用犹豫直接 Kruskal排序成本直接省掉。反过来如果题目给的是邻接矩阵你又不想再单独建边数组那 Prim 矩阵版更顺手。关于“稠密图用 Prim、稀疏图用 Kruskal”这句口诀我用过很久总体来说是对的。但注意 Prim 的堆优化版本并不适合所有稠密图因为稠密图里 push 到堆里的边会非常多反而比 O(V²) 扫描慢。所以具体问题还是要看数据规模不能只背结论。4.3 一个容易被忽略的工程问题排序是 Kruskal 的大头Kruskal 的“把所有边排序”这一步往往比并查集本身更耗时。如果 E 是 10⁶排序时间几乎占整个算法的一半以上。所以在某些需要极致的场景里可以先看看数据结构里有没有“边权范围很小”这个条件如果有可以考虑计数排序的思路按边权分桶这样能把 O(E log E) 的排序优化成近似 O(E W)。不过这只是竞赛题里的优化方向。普通项目里直接使用语言自带的排序然后配合并查集已经足够稳定了。我在实际写代码时更关心的是别让并查集退化排序本身反而是最不需要担心出错的部分。5. 代码落地从伪代码到能跑的 Python 版本5.1 Prim 的优先队列实现下面这份代码处理顶点编号 1 到 n 的情况。adj[u]是 u 的邻居列表元素为(v, w)。import heapq def prim_mst(n, adj): visited [False] * (n 1) heap [] visited[1] True for v, w in adj[1]: heapq.heappush(heap, (w, v)) ans 0 cnt 0 while heap and cnt n - 1: w, u heapq.heappop(heap) if visited[u]: continue visited[u] True ans w cnt 1 for v, nw in adj[u]: if not visited[v]: heapq.heappush(heap, (nw, v)) return ans if cnt n - 1 else -1这里最关键的防御性写法是if visited[u]: continue。因为同一个点可能被 push 多次第一次弹出时标记访问后面再弹出旧记录就必须直接跳过。如果你在堆里弹出节点后不检查 visited很容易把同一条边重复算进答案。5.2 Prim 的邻接矩阵实现当 n 不大且图较稠密时用矩阵版 O(n²) 会比堆更好写也更快def prim_dense(n, cost): visited [False] * n dist [float(inf)] * n dist[0] 0 ans 0 for _ in range(n): t -1 for i in range(n): if not visited[i] and (t -1 or dist[i] dist[t]): t i if dist[t] float(inf): return -1 visited[t] True ans dist[t] for i in range(n): if not visited[i] and cost[t][i] dist[i]: dist[i] cost[t][i] return ans这个版本里dist[v]表示“当前生成树到顶点 v 的最小连接边权”不是从源点到 v 的总路径长度。初始化时dist[0] 0所以第一个顶点会先被选中这是正常的。5.3 Kruskal 的并查集版本class DSU: def __init__(self, n): self.parent list(range(n 1)) self.size [1] * (n 1) def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return False if self.size[ra] self.size[rb]: ra, rb rb, ra self.parent[rb] ra self.size[ra] self.size[rb] return True def kruskal_mst(n, edges): edges.sort(keylambda e: e[2]) dsu DSU(n) ans 0 cnt 0 for u, v, w in edges: if dsu.union(u, v): ans w cnt 1 if cnt n - 1: break return ans if cnt n - 1 else -1这里的find我用了迭代写法加路径压缩而不是递归。递归写法在链很长的时候有可能撑爆栈迭代版更稳。union永远把 size 小的集合挂到 size 大的集合下面这样并查集树高能始终保持很低。6. 常见问题与避坑实录6.1 为什么 Prim 的结果总不对问题多半出在更新那一步我见过最多的错误是把 Prim 的key[v]更新写成了dist[v] w这本质上是在算最短路径而不是最小生成树。还有一种错误是堆里弹出旧记录时没有跳过 visited 节点把重复的边权也累加了。每次调试这种问题我都会在选边循环里临时打印(u, v, w)看选出来的边是不是成环。如果发现答案比预期大优先检查这两处。6.2 Kruskal 的并查集优化不是锦上添花是核心如果不加路径压缩、也不按 size 合并只用一个简单的parent数组Kruskal 在某些测试数据下会非常慢。比如一条链状并查集每次 find 都要走到头复杂度可能退化。按 size 合并和路径压缩一起用后几乎可以认为是常数时间。另外一个细节union返回True/False可以让代码很干净但返回值一定要判断不能盲目累加答案。6.3 带负权边和零权边怎么处理Prim 和 Kruskal 对正负权重没有特殊要求。你可以在图上加权值为负的边算法依然成立因为割定理不依赖权重为正。这和大名鼎鼎的“最短路径里负权边需要小心”是两回事别混淆。最小生成树选的是边的总权重尽量小所以负权边越多越会被优先选中这是正常的。6.4 自环、重边和断开的图自环在 Kruskal 里会被并查集自动忽略因为find(u)和find(v)相等。在 Prim 里用邻接矩阵时要注意cost[i][i]不能设成 0最好设成无穷大否则可能把自环当成一条合法边界边。重边则完全不用处理Kruskal 排序后自然处理Prim 的更新也只会保留更小权重。断开的图是个隐蔽的坑。很多模板代码在循环结束后直接返回 ans如果没有检查已选边数是不是 n-1断开图会输出一个不正确的偏小答案。我在写代码时习惯把返回结果写成ans if cnt n-1 else -1这样接口不会骗人。6.5 一个小习惯用两个算法互相验证我练题的时候有个习惯同一道题先写 Kruskal再写 Prim跑随机小图对拍。这样既能验证自己对两种算法理解的正确性也能在写法上形成肌肉记忆。事实上我后来很多次重构自己代码都是靠两个实现互相查错才定位到问题所在的。min-cut 和 union-find 这类细节你光看是看不出来的必须亲手写一遍再故意制造几个边界用例比如只有一个顶点、图完全断开、所有边权相等才能真正放心。
阅读完成 · 觉得有帮助？
