刷算法题的人几乎都会撞上最小生成树这道坎给定n个点、m条带权边让你选n-1条边把所有点连成一棵树并且让总权重尽量小。铺光缆、接水管、电路板布线、甚至聚类分析里的单链接聚类背后都是同一个模型。这篇文章就想把最小生成树这件事彻底讲透MST 的两个关键性质为什么成立Kruskal 和 Prim 到底怎么实现以及我在实际写代码时踩过的那些坑。之前带过几个实习生看到他们拿到这类题第一反应就是“背模板”。模板当然要会但更要紧的是知道模板为什么这么写。比如find函数为什么要路径压缩Prim 和 Dijkstra 明明长得很像为什么dist的更新方式不一样这些细节一旦想通之后遇到带权图相关的变形题你也能顺手改出来而不是对着网上代码发呆。1. 先把最小生成树这件事说清楚1.1 定义到底在优化什么最小生成树Minimum Spanning Tree的定义不长给定一张带权连通无向图G (V, E)边上有非负权重实际应用中也可能出现负权边我们需要选出|V| - 1条边使得这些边恰好构成一棵树并且所有边权之和最小。注意几个关键词。第一个是“连通无向图”如果图本身不连通那就没有生成树只能退化成最小生成森林。第二个是“树”树意味着任意两点之间有且仅有一条简单路径边数一定是n - 1而且不包含环。第三个是“和最小”这是优化目标。为什么一定要n - 1条边想象一棵树从单点开始长每加入一条新边必然会多连上一个新顶点否则就会形成环。所以从1个点长到n个点正好需要n - 1条边。这个性质在证明算法正确性时经常用到。用个生活化的类比你要在一座山的几个村庄之间修路让任意两个村庄都能互通修路成本按地形高低变化。你现在要决定修哪些路、总成本最低。这个问题不是“找一条最短路”而是“让整个网络连通且总造价最低”。最小生成树就是干这个的。1.2 它和最短路径为什么不是一回事很多初学者会把最小生成树和单源最短路径搞混因为两者都用贪心而且代码框架都带一个dist数组。这两者的本质目标完全不同单源最短路径关心的是从一个固定起点到其他每个点各自的最短距离目标是让单点到多点的距离之和“尽可能各自都短”。最小生成树不关心点对之间的距离只关心整棵树的边权总和最小。举个例子一张图里如果所有边权都是1那么最小生成树的总权重是n - 1。但如果你求从某个点出发到其他点的最短路径树路径总长度可能远大于n - 1因为最短路径树里允许把多条边以“绕路”的方式串起来它每个点到源点都取最短但整体边集并不保证全局总权重最小。所以当你用 Prim 算法时dist[u]的含义是“点u到当前已选生成树集合的最短连接边”而不是“从源点到u的最短路径”。这一点稍后会反复强调也是面试里最容易答错的点。1.3 典型应用场景通信网络铺设多个机房之间要铺光纤每条链路有铺设成本目标是让所有机房连通且总成本最低。电力线路规划多个小区接入电网变电站之间线路造价不同找一个总造价最省的连通方案。电路板布线芯片引脚之间要连线走线长度或打孔代价作为权重。单链接聚类把所有样本看成点两两距离作为边权用 Kruskal 不断合并距离最近的簇本质就是做最小生成树的逐步加边过程。如果你正在准备算法面试最小生成树几乎是图论模块绕不开的内容。刷题平台里带权图的题目很多基础模型就是 MST之后再加限制条件变成次小生成树、瓶颈生成树等进阶题。2. MST 的核心性质凭什么贪心是对的2.1 切割定理Cut Property最小生成树最核心的性质就是切割定理也叫 Cut Property。它说的是把顶点集V任意分成两个非空集合S和V - S所有横跨这两个集合的边里权重最小的那条边一定属于某棵最小生成树。等一下——“一定属于某棵”是什么意思因为如果最小权重边不止一条那其他等权的替代边也可以出现在另一棵最小生成树里。但至少可以保证在所有最小生成树的方案中至少存在一棵包含这条最小横跨边。这个定理是 Kruskal 和 Prim 所有贪心决策的合法性来源。Kruskal 每次选全局最小的边如果这条边连接两个不同连通分量那么这个时刻我们可以把当前已经合并出的某个连通分量看作切割的一侧这条最小边正好横跨切割它被选入某棵 MST 是安全的。Prim 每次从“已选集合”和“未选集合”之间选最小边也完全符合切割定理。用生活化的方式来理解想象你拥有一块地中间有一条河把地块分成两岸。你必须在两岸之间架一座桥不管其他桥怎么规划最便宜的那座桥位置一定会出现在某个最优方案里。因为你总得至少过河一次选最便宜的过河点永远不会吃亏。2.2 环性质Cycle Property与破圈法环性质是切割定理的“对偶版本”图里任何一个环上权重最大的那条边一定不属于任何一棵最小生成树同样如果有多个最大权重的边则至少有一个不属于。为什么假设一棵生成树里包含了环上的最大边e_max。如果你把它从树里删掉树会被分成两个部分这时环上一定有另一条边能把这两个部分重新连起来而且那条边权重比e_max小。换掉之后连通性不变总权重降低说明原来的树不可能是最小生成树。这个性质直接引出了一个很直观的“破圈法”不断在图中找环删掉环上最大的边直到图变成一棵树。理论上可行但实际写代码时要维护环并且找最大边代价太高所以我们通常只用这个性质做算法正确性证明。顺便一提环性质也解释了为什么 Kruskal 在加边时要判断是否成环。如果你试图加入的边让两个已经连通的点再次连通那就形成了一个环而这条新加的边是这个环上最晚被考虑的边。在边按权值升序排列的前提下它一定是环上权重最大的边之一。根据环性质它不可能属于任何 MST直接丢掉就好。2.3 唯一性什么情况下 MST 唯一如果图里所有边的权重互不相同那么最小生成树是唯一的。因为每一步贪心选择的边都被唯一确定不存在等权边造成的分叉。如果存在等权边MST 可能唯一也可能不唯一。例如一条边权全相等的三角形任意两条边都能组成 MST三条不同选择的权重和都一样这时候就有多棵最小生成树。这个结论在题目里经常变成变体给定一张图判断它的最小生成树是否唯一。做法通常是在 Kruskal 的过程中记录同权值的边的数量以及实际被选入 MST 的同权边数量如果某个权值级别下存在一条可选的边没被选入但仍能构成相同权值的生成树则可以判定不唯一。理解唯一性还有个好处当你看到题目里说“边权互不相同”意味着 MST 只有一棵很多关于“次小生成树”的暴力替换思路会简单很多。因为你可以确定唯一的 MST之后枚举非树边去替换树边得到次小方案。3. Kruskal 算法的思路与落地3.1 算法流程与正确性直觉Kruskal 算法的执行步骤可以浓缩成三句话把图中所有边按权重从小到大排序。从最小的边开始遍历如果这条边的两个端点当前不在同一个连通分量里就选中它并合并这两个分量。每成功加入一条边计数器加一当加入的边数达到n - 1时直接结束。正确性的直觉来自切割定理每次加入一条横跨两个不同连通分量的最小边都相当于在当前连通分量的某个切割里选择了最小横跨边。不会把形状锁死也不会错过更优组合。而并查集负责维护“两个端点是不是已经连通”。一个常见误区是认为“每次都选最小边”会不会导致后面的边没得选。不会因为只要不形成环边就可以加。Kruskal 本质上是所有贪心算法里最直观的一种你手里有一堆按价格从低到高的建材从最便宜的买起只要能保证整体连通且无环就买直到凑满n-1条。3.2 最关键的数据结构并查集Kruskal 的代码骨架很简单但性能上限完全取决于并查集写得好不好。并查集Union-Find需要支持两个操作find(x)找到x所在集合的根节点。union(x, y)把x和y所在的两个集合合并。如果find不做路径压缩每次向上找父节点可能退化成一条长链最坏复杂度是O(n)。整个算法跑完可能会变成O(nm)在n, m都是几十万的时候直接超时。路径压缩的思想很朴素既然每次find都要从当前节点一路走到根那就顺便把这条路径上经过的所有节点直接挂到根节点下面下次再找就一步到位。这个优化虽然只是“顺手”但效果极好配合按秩合并Union by Rank可以把单次操作的均摊复杂度降到接近O(1)。按秩合并的意思是合并时把高度较低或规模较小的树挂到高度较高或规模较大的树的根上避免树长高。路径压缩已经能压平大部分查询但加上按秩合并能让最坏情况更可控写起来也不复杂。3.3 Python 代码实现下面这份代码我尽量写得直白方便你直接抄去改class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [1] * n 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): # 按秩合并也可以直接按 size 合并 ra, rb self.find(a), self.find(b) if ra rb: return False if self.rank[ra] self.rank[rb]: ra, rb rb, ra self.parent[rb] ra self.rank[ra] self.rank[rb] return True def kruskal(n, edges): # edges: list of (u, v, w)顶点编号从 0 到 n-1 edges.sort(keylambda x: x[2]) dsu DSU(n) total 0 cnt 0 for u, v, w in edges: if dsu.union(u, v): total w cnt 1 if cnt n - 1: break # 如果 cnt n - 1说明原图不连通不存在生成树 return total if cnt n - 1 else -1这里有个细节find用循环实现还是递归实现都行但递归在 Python 里如果并查集树太深可能触发递归深度限制。所以工程上我更习惯写循环版本虽然代码稍微冗余一点但稳。edges.sort(keylambda x: x[2])也可以换成edges.sort(keylambda e: e[2])总之别写成默认排序因为元组默认会先按u再按v排不是我们想要的顺序。3.4 复杂度分析排序阶段O(m log m)这是 Kruskal 最主要的时间开销。并查集阶段每次union都调用两次find均摊接近O(1)所以总体接近O(m log m)。空间复杂度存边需要O(m)并查集需要O(n)。因此 Kruskal 特别适合稀疏图也就是m相比n^2小得多的图。比如边数m是几十万、顶点数也是几十万排序一次的成本可控并查集依然飞快。一个经验值如果你看到题目给出的图是 “n和m都是10^5级别”那基本就是让你用 Kruskal。如果看到 “n只有几百但是完全图边数接近n^2”那用 Prim 的朴素版反而更稳。4. Prim 算法的思路与落地4.1 从点长成树的视角Prim 和 Kruskal 走的是完全相反的路径。Kruskal 是“从边的角度出发全局找最小边”Prim 是“从点的角度出发让一棵树慢慢长大”。具体流程任选一个起点把它加入生成树集合。维护一个数组dist[u]表示点u到当前生成树集合的最小连接边的权值。初始时起点dist为0其余点的dist为无穷大然后把起点所有邻接边拿来松弛dist。每次从尚未加入生成树的点里选出dist最小的点u把它加入集合并把它的邻接边用于更新其他未选点的dist。重复第三步直到所有点都被加入。累加的dist之和就是最小生成树总权重。这个“选dist最小的点”的直觉也来自切割定理已选集合是一个切割横跨切割的所有边中权值最小的那条必然属于一棵 MST。Prim 每一步就是在找这个横跨切割的最小边。4.2 朴素实现与堆优化的分界线Prim 有两种常见实现。朴素版每次用O(n)遍历找最小dist点然后遍历它的邻接边更新。总复杂度O(n^2 m)适合稠密图m接近n^2。堆优化版用优先队列维护“候选边”或者“候选点”每次取堆顶最小元素。总复杂度O(m log n)适合稀疏图。很多人以为堆优化版一定优于朴素版其实在稠密图里不一定。比如n 1000的完全图m ≈ 500000朴素版每次O(n)扫描1000个点重复1000次总共10^6次操作堆优化版则要做50 万次堆操作加50 万次松弛加上常数因子有时不见得比朴素版快。竞赛里很多出题人就是故意给一个稠密图让你用朴素 Prim 过、堆优化 Prim 也能过但更容易在堆里存很多重复边导致内存膨胀。所以在选型时我的建议很简单稀疏图m与n同数量级Kruskal 优先也可以用堆优化 Prim。稠密图m接近n^2朴素 Prim 优先或者O(m log n)的堆优化 Prim 也可以但要注意堆的重复元素数量。4.3 Python 代码实现朴素版 Prim 写起来最直接对于很多面试场景先把朴素版说清楚再提堆优化效果反而更好。def prim_naive(n, graph): graph: 邻接矩阵graph[u][v] 表示边权不连通记为 inf 顶点编号从 0 到 n-1 INF 10**18 dist [INF] * n used [False] * n dist[0] 0 total 0 for _ in range(n): u -1 min_d INF for i in range(n): if not used[i] and dist[i] min_d: min_d dist[i] u i if u -1: return -1 # 不连通 used[u] True total dist[u] for v in range(n): if not used[v] and graph[u][v] dist[v]: dist[v] graph[u][v] return total重点看最后一段更新代码dist[v] graph[u][v]不是dist[u] graph[u][v]。这把它和 Dijkstra 彻底区分开了。Dijkstra 是“从源点到u的最短距离再加上u-v这条边”而 Prim 是“从当前生成树集合直接连到v的最小边”。堆优化版也很常用我提供一个我常用的写法哲学是“直接存边”堆里存(w, u, v)import heapq def prim_heap(n, adj): adj: list of list[(v, w)] INF 10**18 visited [False] * n dist [INF] * n heap [] # 从 0 号点出发 dist[0] 0 heapq.heappush(heap, (0, 0)) total 0 edge_count 0 while heap and edge_count n: d, u heapq.heappop(heap) if visited[u]: continue visited[u] True total d edge_count 1 for v, w in adj[u]: if not visited[v] and w dist[v]: dist[v] w heapq.heappush(heap, (w, v)) return total if edge_count n else -1这里堆里存放的是“点到当前集合的最小边权”。每次弹出后如果visited[u]已经被置真说明之前有一条更小的边已经把它加入了集合当前这条是过期的直接跳过。这是堆优化算法的经典去重手段别漏掉。4.4 复杂度与注意点朴素版O(n^2 m)空间O(n^2)邻接矩阵。堆优化版O(m log n)空间O(n m)。无论哪种版本如果最终加入集合的点数不等于n就说明图不连通需要返回 -1。另外还有一个小细节如果输入给的图是多重图也就是两点之间有多条边Prim 邻接表存边时可以在松弛判断里自动选择最小的那条Kruskal 则在排序之后自然只处理最小的那条多余的不会影响答案只是多花一点排序时间。5. 两种算法怎么选对比与经验5.1 不同图规模下的选型表我整理了一个简单的选型表查找时可以直接参考场景推荐算法时间复杂度原因稀疏图m接近nKruskalO(m log m)排序成本低并查集极快稠密图m ≈ n^2朴素 PrimO(n^2)不需要维护堆常数小中密度图n很大堆优化 PrimO(m log n)平衡边和点的扫描成本需要输出具体选中的边KruskalO(m log m)边集天然有序输出方便图存在大量重边邻接表 Prim取决于版本自动按最小边权松弛这不是绝对的。在实际比赛中很多人统一用堆优化 Prim 也能打过所有数据。但若遇到n 10000的稠密图朴素O(n^2)只有10^8次操作C 下能过Python 可能会悬。反过来看n 10^5的稀疏图Kruskal 几乎毫无压力。5.2 我的选型习惯我自己的偏好是默认 Kruskal。原因有三个。第一Kruskal 的正确性驱动链路简单边排序之后一路加中途只需要一个并查集不容易写错。第二它在输出具体方案时非常自然union成功的那条边就是树边直接记录即可。第三很多进阶题比如求 MST 里最大边权的最小值、判断 MST 唯一性都是基于 Kruskal 的按序处理能力改动成本低。Prim 我更多用在稠密图尤其是题目给了一个邻接矩阵时。这时候你还要把矩阵转成边表去做 Kruskal不仅多花O(n^2)的空间排序的O(n^2 log n)也很浪费。直接用朴素 Prim 遍历矩阵代码量还更短。5.3 边界情况与变体不连通图两种算法都应该在结束时判断有没有选够n - 1条边没有就返回 -1。次小生成树先求 MST然后枚举每一条非树边把它加进树里形成一个环删掉环上除它之外最大的那条边这样得到一个候选总权重。所有候选里最小的就是次小生成树。这个过程中Kruskal 的输出能力太方便了。瓶颈生成树最小化生成树里的最大边权。它并不要求总权重最小而是要求最大的边尽量小。实际上任意一棵 MST 同时也是某一棵最小瓶颈生成树但反过来不成立。一个经典做法是对边权做二分或直接用 MST。最小生成森林如果图本身不连通可以分别对每个连通分量求 MST总权重求和。并查集的写法天然适合。6. 实操中的常见坑与调试实录6.1 并查集路径压缩和按秩合并缺一不可很多新手写 Kruskal 时并查集只写一个最简单版本def find(x): while parent[x] ! x: x parent[x] return x在链状结构下这个find会非常慢每次都要走到树的最深处。数据量大时明明排序没问题、逻辑也没问题程序就是超时。你以为是算法复杂度不对其实只是并查集没加路径压缩。我一般的建议是就算数据量小也养成写路径压缩的习惯。这不是炫技而是避免你在数据范围改大后突然翻车。6.2 负权边能不能用 MST可以。MST 的定义只要求选出的树边权总和最小不要求边权非负。Kruskal 和 Prim 都能处理负权边。Prim 的朴素实现里dist初始为无穷大然后逐渐被负权边更新变小完全没问题。唯一要注意的是如果你用-1表示不连通而图中恰好有负权边就会出错。所以建议使用一个足够大的INF常量而不是-1来当“无穷大”。6.3 常见错误速查表错误现象可能原因解决办法结果偏大Prim 里把dist[v]写成dist[u] w沿用了 Dijkstra 写法改成min(dist[v], w)死循环堆优化 Prim 里没判断visited反复弹出同一个点visited[u] True加在弹出点处输出边数不够图不连通或break条件写错循环结束后检查cnt n - 1排序后结果不对用元组(u, v, w)排序时没指定key使用lambda e: e[2]显式按权排序内存爆炸稠密图用了边表加堆重复元素过多改朴素 Prim 或限制堆里重复项数据编号从 1 开始数组开小了越界开n 1大小的并查集和边表6.4 自己踩过的两个教训第一次写 Prim 堆优化版本时我把dist更新写成了 Dijkstra 风格结果对拍小数据时发现求出的总权重比真实 MST 大。后来我把dist定义为“到当前集合的最小边”再重新看松弛代码才发现我把两个算法混在一起了。这个错很典型建议初学者把 Prim 的dist语义用荧光笔高亮反复念三遍它不属于某个点它属于一个不断变大的集合。另一次是在处理多重边时我用邻接矩阵存图结果两点之间后读入的边覆盖了先读入的边漏掉了真正的最小边。后来改成存邻接表或用min合并问题就解决了。所以在实现前先明确输入会不会出现“同一对点之间有多条边”如果可能Kruskal 的排序天然会保留最小的那条而邻接矩阵和邻接表都需要做最小值合并。6.5 验证算法正确性的终极武器对拍当你怀疑自己写的 MST 算法有 bug又找不出哪里错最可靠的办法是写一个暴力对照。对小数据量比如n ≤ 8可以枚举所有边集的子集检查是不是一棵生成树连通且无环记录最小总权重。然后随机生成多组带权图把暴力结果和 Kruskal / Prim 的结果做对比。如果有任何一组不一致就手动打印图逐步调试。我记得给一个模拟项目写连通性验证脚本时就是靠这个方法抓到一个隐藏 bug我当时对“不连通图”的判断只放在了 Kruskal 的循环里但 Prim 的朴素版没写u -1的判断结果在一个孤立点上返回了无穷大的总权重。对拍一跑立刻现形。一点经验分享最小生成树这两个算法其实不需要背太多代码。你把切割定理和环性质想明白把并查集写扎实剩下就是语感问题。我在实际工作中用到它的场景远比想象中多比如网络拓扑的连通性优化、传感器网络的节能路由设计甚至某些资源调度问题都能抽象成边权模型。最后再分享一个小习惯拿到任何带权无向图题目先问自己三个问题——图是否连通有没有自环和重边边权是否可能相同这三个信息基本决定了你选用哪种算法以及要不要做特殊判断。做完这些再动手写代码效率会高很多。