我最早被最小生成树MST吸引是很多年前在一家公司做园区网络改造。十几个机房的设备需要全部连通光纤的租赁费按距离算施工队给我一张拓扑图让我算怎么接最省钱。当时我还只会照着最短路径瞎试直到有位前辈丢给我一句话这个问题叫最小生成树你只要记住一句话——在保证所有点连通的前提下让边的总权重最小。Kruskal和Prim就是干这件事的两把刀。这篇文章我会把MST的性质拆开讲透再把Kruskal算法和Prim算法从原理、证明逻辑到代码实现完整过一遍最后用手动演算和实际踩坑经验帮你彻底打通。适合正在学数据结构与算法的学生、准备面试的开发者以及工作中突然要用图论解决问题的工程师。不管你是想应付考试还是想真正理解为什么这两个贪心算法不会翻车这篇文章都能给你一个足够清晰、可以拿去直接用的答案。1. 为什么工程师都要掌握MST从一个布线项目说起1.1 什么是最小生成树一句话定义与三种等价说法最小生成树针对的是连通无向带权图。给定一个图 G (V, E)V是顶点集合E是边集合每条边带一个权重MST要解决的问题是从E中选出若干条边使得所有顶点仍然连通并且选出的边权总和最小。因为n个顶点要连通至少需要n-1条边可以这样想每加入一条边最多让一个新顶点进入连通块第一个顶点不需要边后面n-1个顶点各需要一条边。一个连通且无环、恰好包含n-1条边的子图就是一棵生成树。最小生成树就是所有生成树中总权重最小的那一棵或那几棵。这个概念有几个等价说法理解它们对后面掌握算法很有帮助从连接角度它是把所有点连起来的最省钱的方案从边集角度它是一组不成环的边边数固定为|V|-1且权值和最小从树角度它是一棵以原图顶点为节点、原图边为候选边的树。注意区分MST和最短路径最短路径关心的是两个点之间的最短路程它可能只覆盖少数几个顶点MST关心的是整个图的连通总代价它要把所有顶点都纳入进来。很多人一开始容易把这两个问题搞混实际上它们的思想和适用场景完全不同。1.2 典型应用场景与工程中的直觉MST的应用范围比想象中大得多网络布线机房、基站、传感器节点之间用最少的线缆或租赁费用实现全连通这就是MST最直接的应用电路设计芯片上多个引脚需要连通要尽量减少连线长度和过孔数量聚类分析可以把MST中权重较大的边删掉形成若干个连通分量实现基于密度的聚类图像分割像素作为顶点像素差异作为边权MST的分割结果在视觉上非常自然近似算法许多NP难问题比如旅行商问题可以先求MST再基于MST构造一个不错的近似解。在工程里我接触最多的其实是在满足连通需求下最小化建设成本这一类问题。虽然真实项目中往往还会带上延迟、可靠性等约束MST给的是一个很关键的基准下限——它告诉你没有任何额外约束时理论最低成本是多少。这个数字在方案评审时非常有用。1.3 输入输出与判定标准用形式化的方式定义MST问题输入无向连通图 G (V, E)每条边 e 有非负权重 w(e)实际中权重可以是距离、费用、时延等输出边集 T ⊆ E使得 (V, T) 是连通无环图并且 sum_{e∈T} w(e) 最小。如果图本身不连通就没有生成树这个问题无解。工程里遇到不连通图时通常的做法是先求连通分量每个分量单独做MST最后再人工判断是否要补充连接。还有一种情况是带权图权值可以为负Kruskal和Prim依然能正常工作因为MST算法本身不要求权重非负不过现实中我很少看到负距离这种需求所以这点更多是理论上的完备性。2. MST三大核心性质逐条拆解切分定理、环性质与唯一性2.1 切分定理Cut Property为什么局部最优敢说自己是全局最优切分定理是整个MST算法体系的根基。它的表述是把图G的顶点集合V任意分成两个非空集合 S 和 V-S这条切分线横跨两组顶点之间的所有边叫做横切边如果 e 是所有横切边中权重最小的那条那么 e 一定属于原图的某棵最小生成树。这个性质的证明用的是反证法假设有一棵最小生成树T不包含e。因为T是连通的所以T中必然有一条边 f 连接 S 和 V-S 两侧否则T就被分成了两个互不相连的部分。如果把 f 换成 eT仍然是连通的不会产生环因为 e 跨越切分而原本 f 是唯一跨越切分的树边并且因为 w(e) ≤ w(f)新的生成树权重不会变大。于是存在一棵包含e的MST切分定理成立。这个性质的通俗版本就是你随便拿刀把图切成两半两半之间那条最便宜的边一定可以在某棵最优方案里出现。它给贪心算法提供了底气——我们不需要全局搜索只要每一步都对准某个切分找最小边就能拼出全局最优树。Kruskal和Prim本质上都在反复调用这个定理。2.2 环性质Cycle Property环上最大边可以直接扔掉环性质是切分定理的对偶如果图中存在一个环 C且边 e 是环 C 上权重最大的一条边那么 e 不属于任何一棵最小生成树。证明同样很直观假设某棵MST T包含e。在T中加入环C中除了e之外的一条边 f注意T中存在一条路径连接 f 的两个端点会形成一个环。因为 w(f) w(e)严格大于的情况如果相等则e可以不被选把e从T中删掉再把f加进来仍然是一棵生成树但总权重变小了矛盾。这给我们在选边的时候提供了排除法如果一个边在最坏情况下形成了环且它是这个环上最重的那它永远不可能是最优选择。Kruskal算法在执行过程中会跳过那些加入后成环的边本质上就是因为这些边在当前已经选好的子图里形成了一个环而它们往往不是最优的候选。2.3 唯一性权值全不相等时MST唯一权值相同时要小心一个非常常见的误区是最小生成树是唯一的。其实不唯一唯一性有一个充分条件图中所有边的权值互不相同。如果所有权值都不一样MST的结构是唯一的。如果存在权值相同的边情况就变了可能存在多棵不同的生成树它们的总权重都等于最小值。比如一个正方形四个顶点四条边长都相等那么任意三条边都能构成一棵MST四组解都是最优的。这时候Kruskal或者Prim的执行细节比如相等边谁先谁后会影响你得到具体哪棵树但总权重不变。在工程实践中这种多棵最优解往往会带来麻烦。举个例子某次我们在做多节点组网MST算出来总成本是X但有两棵不同拓扑的树都能达到X其中一个拓扑对某些节点的冗余度更好另一个则延迟更低。如果只把MST唯一记在脑子里就会忽略这个多解问题。所以实操中我建议跑完算法后如果存在等权边额外检查一下另一棵候选树或者在边权设计时加一个极小的扰动来打破相等但在工程里这样做会引入误差需要谨慎。有一点是确定的不管MST有多少棵它们的最小总权重只有一个。Kruskal和Prim只要实现正确得到的总权重一定相等且全局最小。3. Kruskal算法按边贪心为什么能收敛到全局最优3.1 核心思路与正确性依赖的性质Kruskal算法的思路非常朴素把所有边按权重从小到大排序然后依次遍历能加就加。具体步骤是将图中所有边按权重从小到大排序初始化一个空的边集T以及一个记录连通性的并查集按顺序扫描每条边 e (u, v)如果 u 和 v 当前不在同一个连通分量里就选择 e 加入 T并在并查集中合并 u、v 所在集合如果 u 和 v 已经在同一个连通分量里说明加上 e 会形成环直接跳过当 T 中边数达到 n-1 时提前终止如果遍历完所有边还没达到 n-1说明图不连通。为什么贪心选边一定对因为你每一步其实都在隐含地调用切分定理在已经选出的若干连通分量之间画一条切分线当前扫描到的最小的那条横切边就属于最终的MST。换句话说每次合并两个集合并选择最小连接边正是切分定理的逐步应用。整个过程有点像拼图最开始每个点都是独立的块每选一条边就拼上两块直到最后一块完整拼图出现。3.2 并查集实现细节与路径压缩并查集是Kruskal的支柱。并查集维护的是每个顶点当前属于哪个连通块。两个关键操作find(x)找出x所在集合的根节点union(x, y)把x和y所在的两个集合合并。代码实现class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n 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): rx, ry self.find(x), self.find(y) if rx ry: return False # 按秩合并 if self.rank[rx] self.rank[ry]: rx, ry ry, rx self.parent[ry] rx if self.rank[rx] self.rank[ry]: self.rank[rx] 1 return True路径压缩和按秩合并不是可选项没有路径压缩find在最坏情况下会变成O(n)有了路径压缩加按秩合并单次操作的均摊复杂度接近O(1)。这个细节在边数上万以后就能感觉到明显差异。完整Kruskaldef kruskal(n, edges): edges.sort(keylambda x: x[2]) # 按权重排序 dsu DSU(n) mst [] total 0 for u, v, w in edges: if dsu.union(u, v): mst.append((u, v, w)) total w if len(mst) n - 1: break if len(mst) ! n - 1: return None # 图不连通 return mst, total这个实现里有一个细节break条件不能少。如果图是连通的边数达到n-1之后剩下的边再遍历也不会增加边集但提前退出可以省掉很多无意义的find调用。我在写边数达到几百万的稠密图时这个break能带来肉眼可见的速度提升。3.3 复杂度分析与适用场景Kruskal的排序是O(E log E)而E最多是O(V²)所以log E就是O(log V)。并查集操作的总均摊成本接近O(E α(V))其中α(V)是反阿克曼函数增长极慢可以直接当常数看。综合下来Kruskal的时间复杂度是O(E log E)空间复杂度是O(E)存边。Kruskal的主场是稀疏图。当边数E远小于V²时E log E的排序成本可以接受而且它不需要维护复杂的图结构只要给出边列表就能跑。很多实际工程场景里图都是稀疏的每个节点平均连接没几条边所以Kruskal是我个人在工程中首选的原因之一。3.4 扩展最大生成树与最小瓶颈生成树理解了Kruskal的贪心原理之后一些变体问题就迎刃而解最大生成树把排序改成从大到小其余逻辑完全不变最小瓶颈生成树所谓瓶颈是指生成树中最大的那条边权重。Kruskal第一次连通所有节点时的当前边权就是最小瓶颈值而且这个瓶颈生成树就是普通MST这是Kruskal带来的一个额外结论判断图是否连通Kruskal执行完如果边数不足n-1说明原图不连通求每个连通分量的MST在Kruskal遍历过程中每棵并查集树自然对应一个分量的MST。这些扩展在工作中很实用。比如某次做集群拓扑规划要求最远一跳的距离尽量小这正是最小瓶颈生成树问题我用Kruskal跑一遍顺便就把瓶颈值输出了。4. Prim算法从单点生长到整棵树堆优化实战4.1 Prim的点视角从一个顶点开始逐步外扩Prim算法换个角度看问题Kruskal盯着边看Prim盯着已选顶点集合看。步骤是任选一个起点 s把 s 加入集合S维护一个数据结构记录所有连接 S 内顶点和 S 外顶点的横切边每次选择权重最小的横切边 (u, v)其中 u 在 S 内、v 在 S 外把 v 加入 S并选中这条边重复步骤2-3直到所有顶点都进入 S。为什么任意起点都行因为切分定理对任意切分都成立。一开始 S 只有一个点切分线就是这个点和其余所有点之间最小横切边一定在某个MST里之后 S 越来越大每次扩展依然是在做一个合法切分因此每步都安全。Prim和Kruskal本质上是同一个定理的两种不同扫描方式Kruskal是多个连通块同时生长最终合并成一片Prim是一个连通块从单点开始慢慢吞并外部顶点。4.2 朴素实现与堆优化的复杂度差异Prim有两种主流实现朴素版用数组维护每个外部顶点到当前S的最小距离。每次从外部顶点里选距离最小的那个加入S然后更新其他外部顶点的距离。找最小值需要O(V)扫描共V轮每轮更新最多V个顶点所以总复杂度O(V²)。这个写法适合稠密图实现也简单def prim_dense(n, adj): visited [False] * n dist [float(inf)] * n dist[0] 0 parent [-1] * n total 0 for _ in range(n): # 选出未访问且距离最小的点 u min((dist[i], i) for i in range(n) if not visited[i])[1] visited[u] True total dist[u] for v, w in adj[u]: if not visited[v] and w dist[v]: dist[v] w parent[v] u return total注意这里有个细节第4行tmp选择的是当前dist中最小的点而total累加的是dist[u]。dist[u]的含义是u到当前已选集合的最短距离所以累加它正好得到MST总权。堆优化版用优先队列维护外部顶点及其当前最小距离。每次弹出距离最小的顶点如果它已经被访问过就跳过否则加入S并更新邻接顶点。复杂度O(E log V)import heapq def prim_heap(n, adj): visited [False] * n dist [float(inf)] * n dist[0] 0 pq [(0, 0)] # (distance, vertex) total 0 while pq: d, u heapq.heappop(pq) if visited[u]: continue visited[u] True total d for v, w in adj[u]: if not visited[v] and w dist[v]: dist[v] w heapq.heappush(pq, (w, v)) return total堆优化的关键点是同一顶点可能被push多次所以弹出时要检查visited否则会重复处理。我已经不止一次看到有人在比赛里因为这个漏判导致错误。4.3 稠密图用Prim稀疏图用Kruskal选型对比到底用哪个算法我在实际中的选择标准很简单场景推荐算法理由稀疏图E接近VKruskal排序并查集成本低实现简单稠密图E接近V²Prim朴素版O(V²)优于O(E log E)且邻接矩阵实现直观中等密度优先选择堆优化Prim或Kruskal两者都可用取决于代码习惯需要连通分量拆分Kruskal并查集天然得到分量结构嵌入式/内存敏感Prim朴素版邻接矩阵空间大但堆优化需要额外堆内存按实际情况取舍有一个额外的维度Kruskal需要把所有边存下来且排序海量边时内存开销大Prim只需要邻接表堆里最多同时存在E条边但内存波动比Kruskal小。所以当我对边的规模没把握时我倾向于用堆优化Prim因为它不需要排序整个边集只用维护邻接表。提示稀疏还是稠密不要凭感觉。V1000时E2000是稀疏E499500是稠密。先算算V和E的大致量级再选算法。5. 同一张图手动演算两种算法眼见为实5.1 样例图构造为了验证前面讲的理论我构造一个6个顶点、8条边的无向带权图。别记边名直接看权边权重0-140-221-251-3102-433-5114-513-47顶点编号从0到5。这个图是连通的我们手动算一遍看Kruskal和Prim各自会选哪些边。5.2 Kruskal手动演算全过程先把所有边按权重排序4-5权重10-2权重22-4权重30-1权重41-2权重53-4权重71-3权重103-5权重11开始扫描4-54和5不在同一集合选入。当前连通块{4,5}边数10-20和2不在同一集合选入。连通块{0,2}边数22-42的连通块{0,2}和4的连通块{4,5}不在同一集合选入。现在合并成{0,2,4,5}边数30-10和1不在同一集合选入。连通块{0,1,2,4,5}边数41-21和2已经在同一集合里会成环跳过3-43和4不在同一集合选入。所有6个顶点连通边数56-1提前终止。所以Kruskal选出4-5(1)、0-2(2)、2-4(3)、0-1(4)、3-4(7)总权重1234717。注意一个细节排在后面的1-2(5)、1-3(10)、3-5(11)都没被选因为它们要么成环要么轮到时已经不需要了。如果图不连通扫描完所有边后边数会小于5这时候要返回无解。5.3 Prim手动演算全过程我选0号顶点作为起点。初始S{0}。邻接边0-1(4)、0-2(2)。最小的是0-2(2)选入。S{0,2}当前总权2现在S{0,2}看横切边0-1(4)、1-2(5)、2-4(3)。最小的是2-4(3)选入。S{0,2,4}总权235S{0,2,4}横切边0-1(4)、1-2(5)、4-5(1)、3-4(7)。最小的是4-5(1)选入。S{0,2,4,5}总权516S{0,2,4,5}横切边0-1(4)、1-2(5)、1-5(11)、3-4(7)、3-5(11)。最小的是0-1(4)选入。S{0,1,2,4,5}总权6410S{0,1,2,4,5}剩下的外部顶点只有3。横切边1-3(10)、3-4(7)、3-5(11)。最小的是3-4(7)选入。S包含所有顶点总权10717。Prim选出的边0-2(2)、2-4(3)、4-5(1)、0-1(4)、3-4(7)总权重17。和Kruskal一模一样。有意思的是两种算法连选出的边集都完全一致。但这不是必然的——当图里有等权边时两者可能选出不同的树但总权重一定相同。比如把0-2的权重改成和0-1一样都是4那么Kruskal排序时0-1和0-2谁先谁都行选出的边集就可能不同但总权重仍是17。这个现象正好呼应了之前讲的唯一性讨论。5.4 演算带来的直觉收获手动演算一遍之后你对切分定理的反复调用会有更直观的体会。Kruskal每次合并两个集合本质上是在一堆集合之间画切分Prim每次扩展S则是在已选集合和外部顶点之间画切分。它们每一步都选择了某个合法切分下的最小边所以最后能收敛到同一个全局最优。如果你自己手动算一遍我建议你故意把边的顺序打乱再用Kruskal做一次你会发现答案不受边顺序影响排序后自然顺序固定。这也是为什么排序这一步如此重要——没有排序Kruskal就成了一个随便选边的垃圾算法。6. 写代码时我踩过的坑和编码要点6.1 并查集初始化的两个经典错误第一个错误是初始化时把parent数组设成range(n)但没有给rank初始化结果union里比较秩时会出错。第二个错误是find里忘了路径压缩在极端一条链的情况下递归深度能达到V直接爆栈。我在一个模拟项目X里就踩过第二个坑当时节点数有一万边数也比较多没路径压缩的find跑得很吃力经过排查发现每次union都要递归到底改成路径压缩后整个流程从十几秒降到零点几秒。所以这里真的不是细节而是核心性能所在。6.2 提前终止与无解判断Kruskal如果已经选了n-1条边必须break。有一个评测机上的隐藏坑是不break虽然不影响边的集合但会影响性能尤其在边数巨大的评测数据里可能直接TLE。无解判断则是遍历完所有边后mst里的边数不等于n-1说明原图不连通。这里有一个隐蔽情况如果输入图有自环或重边自环始终会被并查集拒绝重边则都参与排序选其中一条即可不会影响正确性。6.3 Prim朴素版的易错细节Prim朴素版最容易错的一行是u min((dist[i], i) for i in range(n) if not visited[i])[1]如果你写成min(dist)但其实需要同时拿到顶点下标就会出问题。另外用float(inf)初始化dist后如果某个顶点和当前S完全不连通dist会一直保持inf总权累加时会变成nan。所以如果图不连通朴素Prim循环里最后会选到inf的顶点这时候应该提前跳出并报告不连通。很多实现里没有处理这个这导致在非连通图上直接出错。6.4 堆优化Prim的重复入堆问题堆优化Prim里同一个顶点可能因为多条更短距离的边而被push多次。如果你只是pop出来就完事没有检查visited那么同一个顶点可能被当作不同顶点重复处理导致MST里出现重复边甚至环。这属于算法步骤没写全的典型错误。一个小优化dist数组里存当前最短距离push前比较w dist[v]才进入可以减少堆里的冗余条目。虽然复杂度不变但常数小很多在大图上有感。6.5 权重为实数或超大整数时的比较陷阱如果边权是浮点数直接用比较通常没问题但要小心精度。更稳妥的方式是用整数权重或者在比较时引入一个EPS。如果是超大整数比如10^18Python的int没有上限所以无所谓但在C里要记得用long long不要用int。还有一个小场景边权可能是0或者负数。前面讲过权值非负不是必须条件但如果你用朴素Primdist初始化成inf就能正确处理负权如果图里有负权环MST依然没问题负权环不影响生成树因为生成树不能有环所以Kruskal和Prim在这种图上依然安全。6.6 工程中的性能调优经验最后分享一条工程经验当你的图特别大比如V到几十万、E到上百万直接用系统排序函数没问题但可以权衡一下是否值得用桶排序之类的手段。实际上E log E在百万级别以内非常快不需要过度优化真正需要优化的是不要每次在Prim里用O(V)去找最小值改用堆。平时写算法题Kruskal的实现通常比堆优化Prim短所以我个人在比赛里默认选Kruskal只有在稠密图明显到E接近V²时才切到Prim朴素版。如果做的是一个必须在嵌入式设备上跑的小工具内存受限制那种情况下我更倾向用邻接矩阵加Prim朴素版因为O(V²)的时间和O(V²)的内存对于几百个节点的图完全可控而且代码极简、没有堆内存碎片。这种选型决策比背Kruskal好还是Prim好的结论重要得多。我在实际项目中还有一个用法是把Kruskal和并查集结合输出最终选中的边集合以及每个连通分量的成员列表这样既拿到了MST又顺手得到了拓扑分组信息。这个需求如果只用Prim还得额外维护一个生成树结构麻烦不少。所以我的建议是掌握两种算法的本质区别再根据你手头问题的约束条件做取舍不要死记硬背二选一。 
长河君 · 2026/10/14 18:20:31 · 阅读 1.2k 最小生成树全解：Kruskal与Prim算法原理、证明与工程实战
我最早被最小生成树MST吸引是很多年前在一家公司做园区网络改造。十几个机房的设备需要全部连通光纤的租赁费按距离算施工队给我一张拓扑图让我算怎么接最省钱。当时我还只会照着最短路径瞎试直到有位前辈丢给我一句话这个问题叫最小生成树你只要记住一句话——在保证所有点连通的前提下让边的总权重最小。Kruskal和Prim就是干这件事的两把刀。这篇文章我会把MST的性质拆开讲透再把Kruskal算法和Prim算法从原理、证明逻辑到代码实现完整过一遍最后用手动演算和实际踩坑经验帮你彻底打通。适合正在学数据结构与算法的学生、准备面试的开发者以及工作中突然要用图论解决问题的工程师。不管你是想应付考试还是想真正理解为什么这两个贪心算法不会翻车这篇文章都能给你一个足够清晰、可以拿去直接用的答案。1. 为什么工程师都要掌握MST从一个布线项目说起1.1 什么是最小生成树一句话定义与三种等价说法最小生成树针对的是连通无向带权图。给定一个图 G (V, E)V是顶点集合E是边集合每条边带一个权重MST要解决的问题是从E中选出若干条边使得所有顶点仍然连通并且选出的边权总和最小。因为n个顶点要连通至少需要n-1条边可以这样想每加入一条边最多让一个新顶点进入连通块第一个顶点不需要边后面n-1个顶点各需要一条边。一个连通且无环、恰好包含n-1条边的子图就是一棵生成树。最小生成树就是所有生成树中总权重最小的那一棵或那几棵。这个概念有几个等价说法理解它们对后面掌握算法很有帮助从连接角度它是把所有点连起来的最省钱的方案从边集角度它是一组不成环的边边数固定为|V|-1且权值和最小从树角度它是一棵以原图顶点为节点、原图边为候选边的树。注意区分MST和最短路径最短路径关心的是两个点之间的最短路程它可能只覆盖少数几个顶点MST关心的是整个图的连通总代价它要把所有顶点都纳入进来。很多人一开始容易把这两个问题搞混实际上它们的思想和适用场景完全不同。1.2 典型应用场景与工程中的直觉MST的应用范围比想象中大得多网络布线机房、基站、传感器节点之间用最少的线缆或租赁费用实现全连通这就是MST最直接的应用电路设计芯片上多个引脚需要连通要尽量减少连线长度和过孔数量聚类分析可以把MST中权重较大的边删掉形成若干个连通分量实现基于密度的聚类图像分割像素作为顶点像素差异作为边权MST的分割结果在视觉上非常自然近似算法许多NP难问题比如旅行商问题可以先求MST再基于MST构造一个不错的近似解。在工程里我接触最多的其实是在满足连通需求下最小化建设成本这一类问题。虽然真实项目中往往还会带上延迟、可靠性等约束MST给的是一个很关键的基准下限——它告诉你没有任何额外约束时理论最低成本是多少。这个数字在方案评审时非常有用。1.3 输入输出与判定标准用形式化的方式定义MST问题输入无向连通图 G (V, E)每条边 e 有非负权重 w(e)实际中权重可以是距离、费用、时延等输出边集 T ⊆ E使得 (V, T) 是连通无环图并且 sum_{e∈T} w(e) 最小。如果图本身不连通就没有生成树这个问题无解。工程里遇到不连通图时通常的做法是先求连通分量每个分量单独做MST最后再人工判断是否要补充连接。还有一种情况是带权图权值可以为负Kruskal和Prim依然能正常工作因为MST算法本身不要求权重非负不过现实中我很少看到负距离这种需求所以这点更多是理论上的完备性。2. MST三大核心性质逐条拆解切分定理、环性质与唯一性2.1 切分定理Cut Property为什么局部最优敢说自己是全局最优切分定理是整个MST算法体系的根基。它的表述是把图G的顶点集合V任意分成两个非空集合 S 和 V-S这条切分线横跨两组顶点之间的所有边叫做横切边如果 e 是所有横切边中权重最小的那条那么 e 一定属于原图的某棵最小生成树。这个性质的证明用的是反证法假设有一棵最小生成树T不包含e。因为T是连通的所以T中必然有一条边 f 连接 S 和 V-S 两侧否则T就被分成了两个互不相连的部分。如果把 f 换成 eT仍然是连通的不会产生环因为 e 跨越切分而原本 f 是唯一跨越切分的树边并且因为 w(e) ≤ w(f)新的生成树权重不会变大。于是存在一棵包含e的MST切分定理成立。这个性质的通俗版本就是你随便拿刀把图切成两半两半之间那条最便宜的边一定可以在某棵最优方案里出现。它给贪心算法提供了底气——我们不需要全局搜索只要每一步都对准某个切分找最小边就能拼出全局最优树。Kruskal和Prim本质上都在反复调用这个定理。2.2 环性质Cycle Property环上最大边可以直接扔掉环性质是切分定理的对偶如果图中存在一个环 C且边 e 是环 C 上权重最大的一条边那么 e 不属于任何一棵最小生成树。证明同样很直观假设某棵MST T包含e。在T中加入环C中除了e之外的一条边 f注意T中存在一条路径连接 f 的两个端点会形成一个环。因为 w(f) w(e)严格大于的情况如果相等则e可以不被选把e从T中删掉再把f加进来仍然是一棵生成树但总权重变小了矛盾。这给我们在选边的时候提供了排除法如果一个边在最坏情况下形成了环且它是这个环上最重的那它永远不可能是最优选择。Kruskal算法在执行过程中会跳过那些加入后成环的边本质上就是因为这些边在当前已经选好的子图里形成了一个环而它们往往不是最优的候选。2.3 唯一性权值全不相等时MST唯一权值相同时要小心一个非常常见的误区是最小生成树是唯一的。其实不唯一唯一性有一个充分条件图中所有边的权值互不相同。如果所有权值都不一样MST的结构是唯一的。如果存在权值相同的边情况就变了可能存在多棵不同的生成树它们的总权重都等于最小值。比如一个正方形四个顶点四条边长都相等那么任意三条边都能构成一棵MST四组解都是最优的。这时候Kruskal或者Prim的执行细节比如相等边谁先谁后会影响你得到具体哪棵树但总权重不变。在工程实践中这种多棵最优解往往会带来麻烦。举个例子某次我们在做多节点组网MST算出来总成本是X但有两棵不同拓扑的树都能达到X其中一个拓扑对某些节点的冗余度更好另一个则延迟更低。如果只把MST唯一记在脑子里就会忽略这个多解问题。所以实操中我建议跑完算法后如果存在等权边额外检查一下另一棵候选树或者在边权设计时加一个极小的扰动来打破相等但在工程里这样做会引入误差需要谨慎。有一点是确定的不管MST有多少棵它们的最小总权重只有一个。Kruskal和Prim只要实现正确得到的总权重一定相等且全局最小。3. Kruskal算法按边贪心为什么能收敛到全局最优3.1 核心思路与正确性依赖的性质Kruskal算法的思路非常朴素把所有边按权重从小到大排序然后依次遍历能加就加。具体步骤是将图中所有边按权重从小到大排序初始化一个空的边集T以及一个记录连通性的并查集按顺序扫描每条边 e (u, v)如果 u 和 v 当前不在同一个连通分量里就选择 e 加入 T并在并查集中合并 u、v 所在集合如果 u 和 v 已经在同一个连通分量里说明加上 e 会形成环直接跳过当 T 中边数达到 n-1 时提前终止如果遍历完所有边还没达到 n-1说明图不连通。为什么贪心选边一定对因为你每一步其实都在隐含地调用切分定理在已经选出的若干连通分量之间画一条切分线当前扫描到的最小的那条横切边就属于最终的MST。换句话说每次合并两个集合并选择最小连接边正是切分定理的逐步应用。整个过程有点像拼图最开始每个点都是独立的块每选一条边就拼上两块直到最后一块完整拼图出现。3.2 并查集实现细节与路径压缩并查集是Kruskal的支柱。并查集维护的是每个顶点当前属于哪个连通块。两个关键操作find(x)找出x所在集合的根节点union(x, y)把x和y所在的两个集合合并。代码实现class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n 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): rx, ry self.find(x), self.find(y) if rx ry: return False # 按秩合并 if self.rank[rx] self.rank[ry]: rx, ry ry, rx self.parent[ry] rx if self.rank[rx] self.rank[ry]: self.rank[rx] 1 return True路径压缩和按秩合并不是可选项没有路径压缩find在最坏情况下会变成O(n)有了路径压缩加按秩合并单次操作的均摊复杂度接近O(1)。这个细节在边数上万以后就能感觉到明显差异。完整Kruskaldef kruskal(n, edges): edges.sort(keylambda x: x[2]) # 按权重排序 dsu DSU(n) mst [] total 0 for u, v, w in edges: if dsu.union(u, v): mst.append((u, v, w)) total w if len(mst) n - 1: break if len(mst) ! n - 1: return None # 图不连通 return mst, total这个实现里有一个细节break条件不能少。如果图是连通的边数达到n-1之后剩下的边再遍历也不会增加边集但提前退出可以省掉很多无意义的find调用。我在写边数达到几百万的稠密图时这个break能带来肉眼可见的速度提升。3.3 复杂度分析与适用场景Kruskal的排序是O(E log E)而E最多是O(V²)所以log E就是O(log V)。并查集操作的总均摊成本接近O(E α(V))其中α(V)是反阿克曼函数增长极慢可以直接当常数看。综合下来Kruskal的时间复杂度是O(E log E)空间复杂度是O(E)存边。Kruskal的主场是稀疏图。当边数E远小于V²时E log E的排序成本可以接受而且它不需要维护复杂的图结构只要给出边列表就能跑。很多实际工程场景里图都是稀疏的每个节点平均连接没几条边所以Kruskal是我个人在工程中首选的原因之一。3.4 扩展最大生成树与最小瓶颈生成树理解了Kruskal的贪心原理之后一些变体问题就迎刃而解最大生成树把排序改成从大到小其余逻辑完全不变最小瓶颈生成树所谓瓶颈是指生成树中最大的那条边权重。Kruskal第一次连通所有节点时的当前边权就是最小瓶颈值而且这个瓶颈生成树就是普通MST这是Kruskal带来的一个额外结论判断图是否连通Kruskal执行完如果边数不足n-1说明原图不连通求每个连通分量的MST在Kruskal遍历过程中每棵并查集树自然对应一个分量的MST。这些扩展在工作中很实用。比如某次做集群拓扑规划要求最远一跳的距离尽量小这正是最小瓶颈生成树问题我用Kruskal跑一遍顺便就把瓶颈值输出了。4. Prim算法从单点生长到整棵树堆优化实战4.1 Prim的点视角从一个顶点开始逐步外扩Prim算法换个角度看问题Kruskal盯着边看Prim盯着已选顶点集合看。步骤是任选一个起点 s把 s 加入集合S维护一个数据结构记录所有连接 S 内顶点和 S 外顶点的横切边每次选择权重最小的横切边 (u, v)其中 u 在 S 内、v 在 S 外把 v 加入 S并选中这条边重复步骤2-3直到所有顶点都进入 S。为什么任意起点都行因为切分定理对任意切分都成立。一开始 S 只有一个点切分线就是这个点和其余所有点之间最小横切边一定在某个MST里之后 S 越来越大每次扩展依然是在做一个合法切分因此每步都安全。Prim和Kruskal本质上是同一个定理的两种不同扫描方式Kruskal是多个连通块同时生长最终合并成一片Prim是一个连通块从单点开始慢慢吞并外部顶点。4.2 朴素实现与堆优化的复杂度差异Prim有两种主流实现朴素版用数组维护每个外部顶点到当前S的最小距离。每次从外部顶点里选距离最小的那个加入S然后更新其他外部顶点的距离。找最小值需要O(V)扫描共V轮每轮更新最多V个顶点所以总复杂度O(V²)。这个写法适合稠密图实现也简单def prim_dense(n, adj): visited [False] * n dist [float(inf)] * n dist[0] 0 parent [-1] * n total 0 for _ in range(n): # 选出未访问且距离最小的点 u min((dist[i], i) for i in range(n) if not visited[i])[1] visited[u] True total dist[u] for v, w in adj[u]: if not visited[v] and w dist[v]: dist[v] w parent[v] u return total注意这里有个细节第4行tmp选择的是当前dist中最小的点而total累加的是dist[u]。dist[u]的含义是u到当前已选集合的最短距离所以累加它正好得到MST总权。堆优化版用优先队列维护外部顶点及其当前最小距离。每次弹出距离最小的顶点如果它已经被访问过就跳过否则加入S并更新邻接顶点。复杂度O(E log V)import heapq def prim_heap(n, adj): visited [False] * n dist [float(inf)] * n dist[0] 0 pq [(0, 0)] # (distance, vertex) total 0 while pq: d, u heapq.heappop(pq) if visited[u]: continue visited[u] True total d for v, w in adj[u]: if not visited[v] and w dist[v]: dist[v] w heapq.heappush(pq, (w, v)) return total堆优化的关键点是同一顶点可能被push多次所以弹出时要检查visited否则会重复处理。我已经不止一次看到有人在比赛里因为这个漏判导致错误。4.3 稠密图用Prim稀疏图用Kruskal选型对比到底用哪个算法我在实际中的选择标准很简单场景推荐算法理由稀疏图E接近VKruskal排序并查集成本低实现简单稠密图E接近V²Prim朴素版O(V²)优于O(E log E)且邻接矩阵实现直观中等密度优先选择堆优化Prim或Kruskal两者都可用取决于代码习惯需要连通分量拆分Kruskal并查集天然得到分量结构嵌入式/内存敏感Prim朴素版邻接矩阵空间大但堆优化需要额外堆内存按实际情况取舍有一个额外的维度Kruskal需要把所有边存下来且排序海量边时内存开销大Prim只需要邻接表堆里最多同时存在E条边但内存波动比Kruskal小。所以当我对边的规模没把握时我倾向于用堆优化Prim因为它不需要排序整个边集只用维护邻接表。提示稀疏还是稠密不要凭感觉。V1000时E2000是稀疏E499500是稠密。先算算V和E的大致量级再选算法。5. 同一张图手动演算两种算法眼见为实5.1 样例图构造为了验证前面讲的理论我构造一个6个顶点、8条边的无向带权图。别记边名直接看权边权重0-140-221-251-3102-433-5114-513-47顶点编号从0到5。这个图是连通的我们手动算一遍看Kruskal和Prim各自会选哪些边。5.2 Kruskal手动演算全过程先把所有边按权重排序4-5权重10-2权重22-4权重30-1权重41-2权重53-4权重71-3权重103-5权重11开始扫描4-54和5不在同一集合选入。当前连通块{4,5}边数10-20和2不在同一集合选入。连通块{0,2}边数22-42的连通块{0,2}和4的连通块{4,5}不在同一集合选入。现在合并成{0,2,4,5}边数30-10和1不在同一集合选入。连通块{0,1,2,4,5}边数41-21和2已经在同一集合里会成环跳过3-43和4不在同一集合选入。所有6个顶点连通边数56-1提前终止。所以Kruskal选出4-5(1)、0-2(2)、2-4(3)、0-1(4)、3-4(7)总权重1234717。注意一个细节排在后面的1-2(5)、1-3(10)、3-5(11)都没被选因为它们要么成环要么轮到时已经不需要了。如果图不连通扫描完所有边后边数会小于5这时候要返回无解。5.3 Prim手动演算全过程我选0号顶点作为起点。初始S{0}。邻接边0-1(4)、0-2(2)。最小的是0-2(2)选入。S{0,2}当前总权2现在S{0,2}看横切边0-1(4)、1-2(5)、2-4(3)。最小的是2-4(3)选入。S{0,2,4}总权235S{0,2,4}横切边0-1(4)、1-2(5)、4-5(1)、3-4(7)。最小的是4-5(1)选入。S{0,2,4,5}总权516S{0,2,4,5}横切边0-1(4)、1-2(5)、1-5(11)、3-4(7)、3-5(11)。最小的是0-1(4)选入。S{0,1,2,4,5}总权6410S{0,1,2,4,5}剩下的外部顶点只有3。横切边1-3(10)、3-4(7)、3-5(11)。最小的是3-4(7)选入。S包含所有顶点总权10717。Prim选出的边0-2(2)、2-4(3)、4-5(1)、0-1(4)、3-4(7)总权重17。和Kruskal一模一样。有意思的是两种算法连选出的边集都完全一致。但这不是必然的——当图里有等权边时两者可能选出不同的树但总权重一定相同。比如把0-2的权重改成和0-1一样都是4那么Kruskal排序时0-1和0-2谁先谁都行选出的边集就可能不同但总权重仍是17。这个现象正好呼应了之前讲的唯一性讨论。5.4 演算带来的直觉收获手动演算一遍之后你对切分定理的反复调用会有更直观的体会。Kruskal每次合并两个集合本质上是在一堆集合之间画切分Prim每次扩展S则是在已选集合和外部顶点之间画切分。它们每一步都选择了某个合法切分下的最小边所以最后能收敛到同一个全局最优。如果你自己手动算一遍我建议你故意把边的顺序打乱再用Kruskal做一次你会发现答案不受边顺序影响排序后自然顺序固定。这也是为什么排序这一步如此重要——没有排序Kruskal就成了一个随便选边的垃圾算法。6. 写代码时我踩过的坑和编码要点6.1 并查集初始化的两个经典错误第一个错误是初始化时把parent数组设成range(n)但没有给rank初始化结果union里比较秩时会出错。第二个错误是find里忘了路径压缩在极端一条链的情况下递归深度能达到V直接爆栈。我在一个模拟项目X里就踩过第二个坑当时节点数有一万边数也比较多没路径压缩的find跑得很吃力经过排查发现每次union都要递归到底改成路径压缩后整个流程从十几秒降到零点几秒。所以这里真的不是细节而是核心性能所在。6.2 提前终止与无解判断Kruskal如果已经选了n-1条边必须break。有一个评测机上的隐藏坑是不break虽然不影响边的集合但会影响性能尤其在边数巨大的评测数据里可能直接TLE。无解判断则是遍历完所有边后mst里的边数不等于n-1说明原图不连通。这里有一个隐蔽情况如果输入图有自环或重边自环始终会被并查集拒绝重边则都参与排序选其中一条即可不会影响正确性。6.3 Prim朴素版的易错细节Prim朴素版最容易错的一行是u min((dist[i], i) for i in range(n) if not visited[i])[1]如果你写成min(dist)但其实需要同时拿到顶点下标就会出问题。另外用float(inf)初始化dist后如果某个顶点和当前S完全不连通dist会一直保持inf总权累加时会变成nan。所以如果图不连通朴素Prim循环里最后会选到inf的顶点这时候应该提前跳出并报告不连通。很多实现里没有处理这个这导致在非连通图上直接出错。6.4 堆优化Prim的重复入堆问题堆优化Prim里同一个顶点可能因为多条更短距离的边而被push多次。如果你只是pop出来就完事没有检查visited那么同一个顶点可能被当作不同顶点重复处理导致MST里出现重复边甚至环。这属于算法步骤没写全的典型错误。一个小优化dist数组里存当前最短距离push前比较w dist[v]才进入可以减少堆里的冗余条目。虽然复杂度不变但常数小很多在大图上有感。6.5 权重为实数或超大整数时的比较陷阱如果边权是浮点数直接用比较通常没问题但要小心精度。更稳妥的方式是用整数权重或者在比较时引入一个EPS。如果是超大整数比如10^18Python的int没有上限所以无所谓但在C里要记得用long long不要用int。还有一个小场景边权可能是0或者负数。前面讲过权值非负不是必须条件但如果你用朴素Primdist初始化成inf就能正确处理负权如果图里有负权环MST依然没问题负权环不影响生成树因为生成树不能有环所以Kruskal和Prim在这种图上依然安全。6.6 工程中的性能调优经验最后分享一条工程经验当你的图特别大比如V到几十万、E到上百万直接用系统排序函数没问题但可以权衡一下是否值得用桶排序之类的手段。实际上E log E在百万级别以内非常快不需要过度优化真正需要优化的是不要每次在Prim里用O(V)去找最小值改用堆。平时写算法题Kruskal的实现通常比堆优化Prim短所以我个人在比赛里默认选Kruskal只有在稠密图明显到E接近V²时才切到Prim朴素版。如果做的是一个必须在嵌入式设备上跑的小工具内存受限制那种情况下我更倾向用邻接矩阵加Prim朴素版因为O(V²)的时间和O(V²)的内存对于几百个节点的图完全可控而且代码极简、没有堆内存碎片。这种选型决策比背Kruskal好还是Prim好的结论重要得多。我在实际项目中还有一个用法是把Kruskal和并查集结合输出最终选中的边集合以及每个连通分量的成员列表这样既拿到了MST又顺手得到了拓扑分组信息。这个需求如果只用Prim还得额外维护一个生成树结构麻烦不少。所以我的建议是掌握两种算法的本质区别再根据你手头问题的约束条件做取舍不要死记硬背二选一。