1. 什么场景下会真正用到最小生成树先抛一个我早年做项目时遇到的实际问题。当时要给一个创业公司的办公区做网络布线一层楼里分布着十几个工位每个工位都需要接到核心交换机上。工位之间走地板的距离、走吊顶的距离、穿墙的难度都不一样简单说就是每两点之间有一个“布线成本”。我的任务是用最低的总成本让所有工位都连通到网络里。这个问题如果没接触过图论第一反应多半是“把每个工位都单独拉一根线到交换机”——成本高得离谱。稍微有点经验的人会想“那就把所有线都铺上再剪掉多余的”——可怎么剪才最省钱这其实就是图论里的经典问题在一张带权无向图中找一棵连接所有顶点的树让所有边的权重之和最小。这棵树就是最小生成树Minimum Spanning Tree简称MST。这类问题太常见了。电网规划要给一片小区建供电线路候选线路有成本要全通电且总造价最低自来水管网要覆盖新城区通信基站之间的光纤要连成一张网甚至做聚类分析时也会用它。可以说凡是“多个点都要连通但连接成本不同求最省钱的连通方案”的需求背后基本都是最小生成树。我知道很多初学者学到这里总感觉最小生成树就是个“背算法”的东西Kruskal一个并查集Prim一个优先队列模板抄一遍就完事。但实际工程里真正值钱的是你能不能在遇到问题时认出这是个MST问题能不能在两种算法里选对那个更合适的能不能处理带负权边、有重边、图很大这些边角情况。这篇文章我就按自己的理解把最小生成树的原理、实现、选型和扩展都拆开讲一遍。内容尽量用大白话代码也给了完整可跑的Python版本希望对正在学图论或者准备面试的读者有点帮助。2. 生成树到底是个什么结构——先把这个弄明白2.1 从“树”到“生成树”再到“最小生成树”图论里的术语容易把人绕晕我先按自己的理解把这条线理顺。树是图的一种特殊形态有n个顶点的连通无向图恰好有n-1条边并且没有环。可以把一棵树想成一个所有节点都能互相连通、但没有任何多余连接的骨架。生成树是在一张连通无向图里选出来的子图它满足三个条件包含原图的全部n个顶点恰好n-1条边是连通的。关键在于原图可能有很多条边生成树只是从中挑出n-1条既不能有环也要保证连通。如果原图每条边带权重不同生成树的总权重不一样。权重总和最小的那棵就是最小生成树。这里有个初学者容易踩的坑生成树必须覆盖所有顶点但它不要求覆盖所有边。也就是说原图里可能某条边权重特别大我们完全可以不选它只要保证连通就行。反过来如果原图本身不连通比如有多个孤立的连通分量那就不存在生成树更不存在最小生成树。这点在实现算法时要格外注意很多题目会特意构造这种“图不连通”的测试数据。2.2 一种直觉解法从全图中“剪掉”边我先说一种笨办法虽然实际没人用它来算但能帮大家建立直觉。假设原图有n个顶点、m条边那么生成树要有n-1条边。我们可以从原来的m条边里删掉多余的m-(n-1)条每删一条边都不能让图断开并且要尽量删掉权重大的边最后留下的就是最小生成树。这种“剪边”思路对应一个著名的定理在一张连通无环图里只要顶点数比边数多1它一定是树。所以从全连通图出发只要删到边数等于n-1且图仍然连通剩下的就是树。但问题是删哪些边能达到总和最小如果只想着“删大的”不一定会得到最优解。因为删除顺序会影响后续能不能继续删、删了会不会断。所以靠直觉兜底可以但真正可靠的是下面两个基础性质。2.3 最小生成树的两条核心性质环路性质和切分性质MST算法那么多归根到底都建立在两条性质上。第一条叫环路性质如果在一个环里有一条边e它是这个环上权重最大的边那么任意一个最小生成树都不包含e。反过来说如果一个环上某条边的权重比环里其他所有边都大那这条边永远是“多余的”选了它总代价只会增加没有任何好处。第二条叫切分性质把图的顶点分成两个非空集合S和V-S这个分割叫一个“切分”。跨过这个切分的所有边里权重最小的那条一定属于某个最小生成树。这个性质比较好理解要让S里的点和V-S里的点连通至少要跨过切分选一条边那当然挑最便宜的那条。这两条性质就是Kruskal和Prim两种算法的底层依据。Kruskal从边的角度出发每次挑全局最小的边如果不成环就加入Prim从点的角度出发每次把离当前树最近的点拉进来。它们一个靠环路性质保证安全一个靠切分性质保证安全殊途同归。这里我想特别强调这两条性质的“证明”不重要重要的是理解“局部最优不会毁掉全局最优”这件事。和很多贪心算法不同最小生成树的贪心是严格正确的因为我们面对的问题有“最优子结构”和“贪心选择性质”双重保障。后面讲算法代码时你会看到每一步都在利用这两条性质做决策。3. Kruskal 算法排序边的贪心并查集的天下3.1 为什么按边权排序后依次选就能得到最优Kruskal的思想极其简单简单到我第一次学的时候怀疑它是不是有点“太笨了”。步骤只有四步把所有边按权重从小到大排序。准备一个空的边集合。从小到大遍历每条边如果这条边的两个端点当前不连通就把这条边加入集合。当集合里有n-1条边时停止。这个集合就是最小生成树。为什么这样就能得到最优用切分性质来看排序后当前最小的那条边连接的是两个不同的“连通块”这两个连通块之间所有边里它一定是最小的——因为更小的边要么已经被处理过、要么因为成环被跳过了。换句话说它永远满足“跨过某个切分的最小边”这个条件纳入它不会错。而“如果两个端点已经连通就跳过”这一步其实是环路性质在发挥作用如果已经连通再加这条边就必然成环而被我们跳过的边在它所在的那个环里往往就是权重最大的边之一留着它绝对不会是最优解。这就是为什么Kruskal不需要回溯、不需要调整一次遍历完就是正确答案。3.2 并查集是 Kruskal 的灵魂Kruskal的实现难点不在排序而在“判断两个端点是否连通”。如果每次都用DFS/BFS去遍历图复杂度会退化得非常难看。这里必须用并查集Union-Find。并查集的核心能力就两个find(x)找到x所在集合的代表元素。union(x, y)把x和y所在的两个集合合并。在Kruskal语境下每个连通块就是一个集合。遍历一条边(u, v)时先find(u)和find(v)如果代表相同说明u和v已经在同一个连通块里加边会成环跳过否则union这两个集合并把边加入结果。并查集有两个关键优化路径压缩和按秩合并两个都加上后单次操作的均摊复杂度接近O(1)。路径压缩指的是find时把沿途节点直接挂到根上按秩合并指的是union时把“矮树”接到“高树”上防止树退化成链表。图论的很多算法里并查集都是配角但在MST问题里它直接决定了算法的可行性这个点值得单独说一句。3.3 Kruskal 的完整 Python 实现下面是一份可以直接跑的Kruskal实现我加了详细的注释。输入格式采用邻接表结构edges列表里每个元素是(weight, u, v)三元组顶点编号从0到n-1。class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [1] * 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): fx, fy self.find(x), self.find(y) if fx fy: return False # 按秩合并 if self.rank[fx] self.rank[fy]: fx, fy fy, fx self.parent[fy] fx self.rank[fx] self.rank[fy] return True def kruskal(n, edges): # 1. 按边权排序 edges.sort(keylambda x: x[0]) dsu DSU(n) mst_weight 0 mst_edges [] for w, u, v in edges: # 2. 不成环才加入 if dsu.union(u, v): mst_weight w mst_edges.append((u, v, w)) # 3. 收集够 n-1 条边就结束 if len(mst_edges) n - 1: break # 4. 如果边数不足 n-1说明图不连通 if len(mst_edges) ! n - 1: return None, -1 return mst_edges, mst_weight这段代码有几个细节值得注意。第一edges.sort(keylambda x: x[0])这种写法是按权重排序Python里也可以直接用元组排序因为元组默认按第一个元素排但显示写出key会更清晰。第二union返回False说明两个点已经在同一集合用这个返回值简化了逻辑。第三提前跳出循环的条件是收集到n-1条边这是树的基本性质再多一条就会成环。实际测试时我用了一个简单的例子验证3个顶点边分别是(1, 0, 1)、(2, 1, 2)、(3, 0, 2)。排序后先选(1, 0, 1)再选(2, 1, 2)此时两条边的总权重是3正好是正确答案。第三条边(3, 0, 2)因为0和2已经连通被跳过结果正确。3.4 Kruskal 的时间复杂度拆解Kruskal的复杂度主要由排序主导。排序需要O(m log m)。并查集部分每次操作几乎常数m条边最多遍历一遍所以是O(m·α(n))其中α(n)是反阿克曼函数增长极慢工程上可以当成常数。整体时间复杂度是O(m log m)。如果图的边数m很大接近完全图这个复杂度会比较高如果m很小稀疏图Kruskal会非常快。而Prim算法的时间复杂度在不同实现下差异很大后面讲Prim时会专门对比。4. Prim 算法从点出发的切分扩展法4.1 从一个点开始“长”出一棵树Kruskal是“选边”Prim是“加点”。思路是随便选一个起点把它加进MST集合然后反复找连接“已在集合中的点”和“不在集合中的点”的最小边把这条边和它对应的新点一起加进来直到所有点都进集合。用切分性质来理解每次迭代把“已在MST中的点”看成S“不在的”看成V-S这是一个切分。跨过这个切分的所有边里最小那条就是应该选的边。所以Prim的本质就是反复利用切分性质每次把当前边界上最近的点拉进来。Prim有两种常见实现。朴素版本用数组维护每个点到当前树的最小距离每一轮扫描所有点找最小值适合稠密图。堆优化版本用优先队列维护候选边适合稀疏图。这里我重点讲堆优化版本因为它的代码在实际面试和工程里更常见。4.2 堆优化的 Prim 实现堆优化Prim的思路维护一个最小堆堆里放边权, 点候选从某个起点开始每次弹出最小边权的点如果这个点已经在MST集合里就跳过否则加入MST并把这个点所有邻接边作为新候选压入堆。import heapq def prim(n, graph): # graph 是邻接表: graph[u] [(v, w), ...] visited [False] * n heap [(0, 0)] # 从顶点0开始权重0 mst_weight 0 mst_edges [] count 0 while heap and count n: w, u heapq.heappop(heap) if visited[u]: continue visited[u] True mst_weight w count 1 if u ! 0: # 第一条边是起点自己不需要记 mst_edges.append((prev[u], u, w)) for v, nw in graph[u]: if not visited[v]: heapq.heappush(heap, (nw, v)) if count ! n: return None, -1 # 图不连通 return mst_edges, mst_weight等等上面代码里有个问题——我想记录具体边的时候需要知道“这个点是被哪条边拉进来的”。堆里只存了权重和点没存来源。需要稍微改一下堆里存边权, 来源点, 当前点这样才能还原出完整的MST边集import heapq def prim(n, graph): visited [False] * n heap [(0, -1, 0)] # (边权, 来源点, 当前点)起点来源用 -1 mst_weight 0 mst_edges [] count 0 while heap and count n: w, src, u heapq.heappop(heap) if visited[u]: continue visited[u] True mst_weight w count 1 if src ! -1: mst_edges.append((src, u, w)) for v, nw in graph[u]: if not visited[v]: heapq.heappush(heap, (nw, u, v)) if count ! n: return None, -1 return mst_edges, mst_weight这里有一个关键点堆里可能同时存在同一顶点的多个候选比如点a可能被邻接点b和c分别以不同权重压入堆。弹出时如果该点已经被访问过说明已经有更优的路径先到达了它直接跳过即可。这种“懒删除”策略是堆优化Prim的常见实现方式代码简洁代价是堆里会有少量冗余元素内存占用略高但实际性能依然很好。4.3 Prim 的复杂度分析以及为什么稠密图用朴素版更稳堆优化Prim的时间复杂度是O(m log n)。每一条边最多被压入堆一次另一方向也会被压入所以实际是O(m log n)每次堆操作O(log n)。朴素Prim的复杂度是O(n^2)每轮扫描n个点找最小值总共n轮。在稠密图m接近n^2里O(m log n)其实比O(n^2)更慢因为m log n n^2 log n n^2。这就是为什么很多人说“稠密图用朴素Prim稀疏图用Kruskal或堆优化Prim”。这个结论不是谁拍脑袋定的是复杂度推导出来的。平时刷题时看到n是10^4级别而边是10^7级别优先考虑朴素Prim看到n很大但边很少优先考虑Kruskal。4.4 两个小坑重边和自环Prim实现还有个容易被忽视的坑重边。如果两个顶点之间有多次连接、权重不同堆优化Prim天然能处理——它会把所有边都压入堆最终只保留最小的那条。但朴素Prim用数组存最小距离时如果初始化时直接覆盖而不是取min就可能出错。正确做法是初始化时取dist[v] min(dist[v], w)。自环同理自环边的权重如果比当前dist大不影响但如果不小心用自环覆盖了正常边的距离就会出现“点已经在树里了却还在更新自己距离”这类诡异问题。这些边界情况在做竞赛题时非常常见。我印象里不少题目喜欢在测试数据里塞重边专门钓那些没处理取min的选手。所以写模板时建议养成习惯不管什么方法读边时都加一句dist[a][b] min(dist[a][b], w)一劳永逸。5. 两种算法如何选——决策表与几种边界情况的实战处理5.1 Kruskal 与 Prim 的完整对比很多教材喜欢说“两种算法都能求MST”但实际工程里选错算法可能让程序跑几分钟和跑几秒钟的差别。我把关键差异整理成了一张表对比维度KruskalPrim堆优化Prim朴素核心思想按边排序贪心选边从点出发切分扩展同左主要数据结构并查集优先队列堆数组维护最小距离时间复杂度O(m log m)O(m log n)O(n^2)适合场景稀疏图m接近n稀疏图/中等稠密图m接近n^2实现难度较低中等较低是否需要邻接表只需边集需要邻接表需要邻接矩阵或邻接表处理重边排序后自然处理堆里重复入跳过早需显式取min处理图不连通边数不足检测count ! n 检测检查dist无穷大直观结论如果m很大约n^2级别用朴素Prim如果m接近n用Kruskal如果n和m都是10^5级别堆优化Prim和Kruskal都行但Kruskal代码更短、更好调试。我自己的实际经验刷题和面试时Kruskal往往比Prim更快写对因为并查集模板很固定排序也简单。Prim如果要用堆优化还要注意堆里冗余元素的处理容易在边界条件上翻车。所以如果题目没有明确要求用哪种我默认优先写Kruskal。但这不意味着Prim可以不学有些题的图是“几乎完全图”比如任意两点都有边这时Kruskal要排序千万条边而朴素Prim复杂度更优用对算法能省不少时间。5.2 图不连通时的处理MST有一个前提图必须连通。实际数据却不一定讲道理。Kruskal实现里我判断len(mst_edges) ! n - 1作为不连通标志这利用了“n个顶点的树恰好有n-1条边”的性质。如果图有多个连通分量Kruskal只能生成一个分量的生成森林边数必然少于n-1。Prim实现里则用count ! n判断因为如果某个点始终无法被访问到说明它和起点不在同一个连通分量里。还有一种情况是一开始图就不是连通的但题目不保证。这时Kruskal返回None调用方需要处理“没有MST”的情形。竞赛里常见的是输出“impossible”或者-1。很多人写了Kruskal就把这个判断漏了结果遇到不连通数据直接数组越界或者计算出错误答案排查时很费劲。5.3 负权边能让 MST 失效吗一个比较常见的问题是图里有负权边MST会受影响吗答案是不会。最小生成树只关心总权重最小负权边只要不形成环、能降总权重就可以正常选。所有基于切分性质和环路性质的证明都不要求权值非负Prim和Kruskal都能处理负权边。这里和最短路径的Dijkstra算法不太一样。Dijkstra遇到负权边会失效但MST算法不会因为MST不需要维护“从起点到某点的距离”这种累计量它只比较单条边的权重。初学者容易把这两个问题混在一起把Dijkstra的局限错误地迁移到MST上。其实只要记住MST问的是“树的权重总和”Dijkstra问的是“路径的权重总和”后者受负权影响前者不受。6. 从“求最小”到“求次小”再到真实工程场景6.1 最大生成树和次小生成树MST的变体不少这里说两个最常见的。第一个是最大生成树。直接把所有边权重取负号再跑一遍Kruskal或Prim算出来的就是最大生成树。因为排序时取负号等价于按原权值从大到小排整个贪心逻辑不变。比如在“要最大化连接质量”的场景比如带宽要求最大生成树很有用。第二个是次小生成树。次小生成树是权重第二小的生成树它可以和MST相同也可以不同。求法比较经典先求出MST然后枚举每一条不属于MST的边e(u, v)如果把e加进MST会形成一个环在环上找一条除e外最大的边f它在MST里用e替换f得到一个新生成树权重是MST总权重 - weight(f) weight(e)。对所有非树边做这种替换取权重最小且大于MST权重的结果就是严格次小生成树。实现这个思路时找“环上最大的边”需要树上倍增等技巧代码量比较大但思路本身值得理解。它和“最小生成树唯一性”的问题也相关——如果每一条非树边替换后的权重都大于等于MST权重那么MST唯一如果存在某条非树边替换后权重等于MST权重说明MST不唯一。有些面试题喜欢围绕“MST是否唯一”做文章本质上就是在考这个替换逻辑。6.2 最小生成树在聚类和图像分割里的应用MST不只是算法题。在无监督学习里有一种叫单链接聚类single-linkage clustering的方法本质就是MST。思路是把高维数据点看成图的顶点点与点的距离看成边的权重构造出MST。然后从总权重大的边开始剪剪断几条就把数据分成了几个簇。因为MST保留了“最紧密的连接”剪掉大的边相当于断开最不相似的连接剩下的连通块就是聚类结果。图像分割里也有类似用法。把每个像素看成顶点相邻像素的亮度差看成边权构造MST然后根据亮度差阈值剪断某些边得到分割区域。这类方法叫基于图割的分割当年在计算机视觉里火过一阵。我第一次看到MST用在图像领域时还挺惊讶因为它看起来就是个离散数学工具但实际可以用来处理连续图像数据。6.3 网线布线时的一个实战教训回到开头那个布线项目。我当时用Kruskal算完最小生成树让施工队按方案布线结果发现有个致命问题MST保证了总成本最低但它完全不考虑“延迟”。MST里两个点之间的通信路径可能绕很远实际办公场景里工位A和工位B之间可能经常要传大文件绕远路会导致网络延迟高体验差。这个问题让我意识到MST只是一种“成本约束下的最优解”但工程里往往还有性能约束、可靠性约束和实用性约束。实践中更合理的设计是先保证MST作为骨架再根据重要节点之间的通信需求额外地加几条关键直连链路形成一个“MST少量冗余边”的混合拓扑。这个例子说明算法给出的是数学最优解是否等于工程最优解要结合场景判断不能盲目套用。不过话说回来正因为MST能用极低的算法复杂度给出一套“足够好”的初始方案它在工程规划阶段仍然非常实用。哪怕最终拓扑要调整MST也是一个极佳的起点。7. 我踩过的几个坑和给你避坑建议写到这里MST的主要内容基本讲完了最后分享几个我实际编码时踩过的坑。第一个坑是Kruskal里忘了处理“图不连通”的情况。我早期比赛时有一次把n个点、m条边的数据测了前几组都对到后面有一组图本身不连通程序直接返回了一个“边数不足”的数组后续逻辑全崩。后来我写Kruskal时总是会在循环结束后检查len(mst_edges) n - 1不满足就直接返回异常或-1再也没犯过同样的错误。第二个坑是重边。Prim的朴素实现里如果初始化dist数组时不取min重边会导致dist被覆盖成较大值导致算法选了错误的边。这个问题最隐蔽因为小数据里重边不多跑起来也没报错就是答案不对。现在我在处理图的输入时只要涉及“求两个点之间的最小距离/最小边权”这类需求一律写min这已经成了肌肉记忆。第三个坑是堆优化Prim里忘了跳过已访问节点。如果弹出堆顶时发现该点已经在MST里就直接continue否则会把同一个点重复加入MST导致结果含环或者边数超过n-1。这个问题我在手写代码时遇过好几次每次都想骂自己“怎么又忘了”。其实原因很简单同一顶点可能被多个邻居以不同权重压入堆堆里同时存在多条候选弹出顺序取决于权重后弹出的必然是无效的必须跳过。第四个是负权边的问题。虽然我说MST算法能处理负权边但有个细节如果图里有负权边且允许“必须全选”MST仍是正确的但如果你在“剪边”思路里理解MST可能会被负权边绕晕。记住一条简单的判断标准最小生成树选的是“哪些边连成树”不是“从起点到某点的距离”所以负权不影响。最后给大家一个练手建议想真正理解MST别只看代码拿一张纸画一个带权重的图手动模拟一遍Kruskal的选边过程。我当年就是这么干的模拟了三张图之后再理解Prim就顺畅多了。最小生成树是个特别经典的贪心算法思路一旦通了后面学习其它图论算法比如最短路、网络流也能触类旁通值得多花点时间把它弄扎实。 
长河君 · 2026/10/6 4:50:26 · 阅读 1.2k 从布线到聚类：最小生成树原理、Kruskal与Prim实战解析
1. 什么场景下会真正用到最小生成树先抛一个我早年做项目时遇到的实际问题。当时要给一个创业公司的办公区做网络布线一层楼里分布着十几个工位每个工位都需要接到核心交换机上。工位之间走地板的距离、走吊顶的距离、穿墙的难度都不一样简单说就是每两点之间有一个“布线成本”。我的任务是用最低的总成本让所有工位都连通到网络里。这个问题如果没接触过图论第一反应多半是“把每个工位都单独拉一根线到交换机”——成本高得离谱。稍微有点经验的人会想“那就把所有线都铺上再剪掉多余的”——可怎么剪才最省钱这其实就是图论里的经典问题在一张带权无向图中找一棵连接所有顶点的树让所有边的权重之和最小。这棵树就是最小生成树Minimum Spanning Tree简称MST。这类问题太常见了。电网规划要给一片小区建供电线路候选线路有成本要全通电且总造价最低自来水管网要覆盖新城区通信基站之间的光纤要连成一张网甚至做聚类分析时也会用它。可以说凡是“多个点都要连通但连接成本不同求最省钱的连通方案”的需求背后基本都是最小生成树。我知道很多初学者学到这里总感觉最小生成树就是个“背算法”的东西Kruskal一个并查集Prim一个优先队列模板抄一遍就完事。但实际工程里真正值钱的是你能不能在遇到问题时认出这是个MST问题能不能在两种算法里选对那个更合适的能不能处理带负权边、有重边、图很大这些边角情况。这篇文章我就按自己的理解把最小生成树的原理、实现、选型和扩展都拆开讲一遍。内容尽量用大白话代码也给了完整可跑的Python版本希望对正在学图论或者准备面试的读者有点帮助。2. 生成树到底是个什么结构——先把这个弄明白2.1 从“树”到“生成树”再到“最小生成树”图论里的术语容易把人绕晕我先按自己的理解把这条线理顺。树是图的一种特殊形态有n个顶点的连通无向图恰好有n-1条边并且没有环。可以把一棵树想成一个所有节点都能互相连通、但没有任何多余连接的骨架。生成树是在一张连通无向图里选出来的子图它满足三个条件包含原图的全部n个顶点恰好n-1条边是连通的。关键在于原图可能有很多条边生成树只是从中挑出n-1条既不能有环也要保证连通。如果原图每条边带权重不同生成树的总权重不一样。权重总和最小的那棵就是最小生成树。这里有个初学者容易踩的坑生成树必须覆盖所有顶点但它不要求覆盖所有边。也就是说原图里可能某条边权重特别大我们完全可以不选它只要保证连通就行。反过来如果原图本身不连通比如有多个孤立的连通分量那就不存在生成树更不存在最小生成树。这点在实现算法时要格外注意很多题目会特意构造这种“图不连通”的测试数据。2.2 一种直觉解法从全图中“剪掉”边我先说一种笨办法虽然实际没人用它来算但能帮大家建立直觉。假设原图有n个顶点、m条边那么生成树要有n-1条边。我们可以从原来的m条边里删掉多余的m-(n-1)条每删一条边都不能让图断开并且要尽量删掉权重大的边最后留下的就是最小生成树。这种“剪边”思路对应一个著名的定理在一张连通无环图里只要顶点数比边数多1它一定是树。所以从全连通图出发只要删到边数等于n-1且图仍然连通剩下的就是树。但问题是删哪些边能达到总和最小如果只想着“删大的”不一定会得到最优解。因为删除顺序会影响后续能不能继续删、删了会不会断。所以靠直觉兜底可以但真正可靠的是下面两个基础性质。2.3 最小生成树的两条核心性质环路性质和切分性质MST算法那么多归根到底都建立在两条性质上。第一条叫环路性质如果在一个环里有一条边e它是这个环上权重最大的边那么任意一个最小生成树都不包含e。反过来说如果一个环上某条边的权重比环里其他所有边都大那这条边永远是“多余的”选了它总代价只会增加没有任何好处。第二条叫切分性质把图的顶点分成两个非空集合S和V-S这个分割叫一个“切分”。跨过这个切分的所有边里权重最小的那条一定属于某个最小生成树。这个性质比较好理解要让S里的点和V-S里的点连通至少要跨过切分选一条边那当然挑最便宜的那条。这两条性质就是Kruskal和Prim两种算法的底层依据。Kruskal从边的角度出发每次挑全局最小的边如果不成环就加入Prim从点的角度出发每次把离当前树最近的点拉进来。它们一个靠环路性质保证安全一个靠切分性质保证安全殊途同归。这里我想特别强调这两条性质的“证明”不重要重要的是理解“局部最优不会毁掉全局最优”这件事。和很多贪心算法不同最小生成树的贪心是严格正确的因为我们面对的问题有“最优子结构”和“贪心选择性质”双重保障。后面讲算法代码时你会看到每一步都在利用这两条性质做决策。3. Kruskal 算法排序边的贪心并查集的天下3.1 为什么按边权排序后依次选就能得到最优Kruskal的思想极其简单简单到我第一次学的时候怀疑它是不是有点“太笨了”。步骤只有四步把所有边按权重从小到大排序。准备一个空的边集合。从小到大遍历每条边如果这条边的两个端点当前不连通就把这条边加入集合。当集合里有n-1条边时停止。这个集合就是最小生成树。为什么这样就能得到最优用切分性质来看排序后当前最小的那条边连接的是两个不同的“连通块”这两个连通块之间所有边里它一定是最小的——因为更小的边要么已经被处理过、要么因为成环被跳过了。换句话说它永远满足“跨过某个切分的最小边”这个条件纳入它不会错。而“如果两个端点已经连通就跳过”这一步其实是环路性质在发挥作用如果已经连通再加这条边就必然成环而被我们跳过的边在它所在的那个环里往往就是权重最大的边之一留着它绝对不会是最优解。这就是为什么Kruskal不需要回溯、不需要调整一次遍历完就是正确答案。3.2 并查集是 Kruskal 的灵魂Kruskal的实现难点不在排序而在“判断两个端点是否连通”。如果每次都用DFS/BFS去遍历图复杂度会退化得非常难看。这里必须用并查集Union-Find。并查集的核心能力就两个find(x)找到x所在集合的代表元素。union(x, y)把x和y所在的两个集合合并。在Kruskal语境下每个连通块就是一个集合。遍历一条边(u, v)时先find(u)和find(v)如果代表相同说明u和v已经在同一个连通块里加边会成环跳过否则union这两个集合并把边加入结果。并查集有两个关键优化路径压缩和按秩合并两个都加上后单次操作的均摊复杂度接近O(1)。路径压缩指的是find时把沿途节点直接挂到根上按秩合并指的是union时把“矮树”接到“高树”上防止树退化成链表。图论的很多算法里并查集都是配角但在MST问题里它直接决定了算法的可行性这个点值得单独说一句。3.3 Kruskal 的完整 Python 实现下面是一份可以直接跑的Kruskal实现我加了详细的注释。输入格式采用邻接表结构edges列表里每个元素是(weight, u, v)三元组顶点编号从0到n-1。class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [1] * 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): fx, fy self.find(x), self.find(y) if fx fy: return False # 按秩合并 if self.rank[fx] self.rank[fy]: fx, fy fy, fx self.parent[fy] fx self.rank[fx] self.rank[fy] return True def kruskal(n, edges): # 1. 按边权排序 edges.sort(keylambda x: x[0]) dsu DSU(n) mst_weight 0 mst_edges [] for w, u, v in edges: # 2. 不成环才加入 if dsu.union(u, v): mst_weight w mst_edges.append((u, v, w)) # 3. 收集够 n-1 条边就结束 if len(mst_edges) n - 1: break # 4. 如果边数不足 n-1说明图不连通 if len(mst_edges) ! n - 1: return None, -1 return mst_edges, mst_weight这段代码有几个细节值得注意。第一edges.sort(keylambda x: x[0])这种写法是按权重排序Python里也可以直接用元组排序因为元组默认按第一个元素排但显示写出key会更清晰。第二union返回False说明两个点已经在同一集合用这个返回值简化了逻辑。第三提前跳出循环的条件是收集到n-1条边这是树的基本性质再多一条就会成环。实际测试时我用了一个简单的例子验证3个顶点边分别是(1, 0, 1)、(2, 1, 2)、(3, 0, 2)。排序后先选(1, 0, 1)再选(2, 1, 2)此时两条边的总权重是3正好是正确答案。第三条边(3, 0, 2)因为0和2已经连通被跳过结果正确。3.4 Kruskal 的时间复杂度拆解Kruskal的复杂度主要由排序主导。排序需要O(m log m)。并查集部分每次操作几乎常数m条边最多遍历一遍所以是O(m·α(n))其中α(n)是反阿克曼函数增长极慢工程上可以当成常数。整体时间复杂度是O(m log m)。如果图的边数m很大接近完全图这个复杂度会比较高如果m很小稀疏图Kruskal会非常快。而Prim算法的时间复杂度在不同实现下差异很大后面讲Prim时会专门对比。4. Prim 算法从点出发的切分扩展法4.1 从一个点开始“长”出一棵树Kruskal是“选边”Prim是“加点”。思路是随便选一个起点把它加进MST集合然后反复找连接“已在集合中的点”和“不在集合中的点”的最小边把这条边和它对应的新点一起加进来直到所有点都进集合。用切分性质来理解每次迭代把“已在MST中的点”看成S“不在的”看成V-S这是一个切分。跨过这个切分的所有边里最小那条就是应该选的边。所以Prim的本质就是反复利用切分性质每次把当前边界上最近的点拉进来。Prim有两种常见实现。朴素版本用数组维护每个点到当前树的最小距离每一轮扫描所有点找最小值适合稠密图。堆优化版本用优先队列维护候选边适合稀疏图。这里我重点讲堆优化版本因为它的代码在实际面试和工程里更常见。4.2 堆优化的 Prim 实现堆优化Prim的思路维护一个最小堆堆里放边权, 点候选从某个起点开始每次弹出最小边权的点如果这个点已经在MST集合里就跳过否则加入MST并把这个点所有邻接边作为新候选压入堆。import heapq def prim(n, graph): # graph 是邻接表: graph[u] [(v, w), ...] visited [False] * n heap [(0, 0)] # 从顶点0开始权重0 mst_weight 0 mst_edges [] count 0 while heap and count n: w, u heapq.heappop(heap) if visited[u]: continue visited[u] True mst_weight w count 1 if u ! 0: # 第一条边是起点自己不需要记 mst_edges.append((prev[u], u, w)) for v, nw in graph[u]: if not visited[v]: heapq.heappush(heap, (nw, v)) if count ! n: return None, -1 # 图不连通 return mst_edges, mst_weight等等上面代码里有个问题——我想记录具体边的时候需要知道“这个点是被哪条边拉进来的”。堆里只存了权重和点没存来源。需要稍微改一下堆里存边权, 来源点, 当前点这样才能还原出完整的MST边集import heapq def prim(n, graph): visited [False] * n heap [(0, -1, 0)] # (边权, 来源点, 当前点)起点来源用 -1 mst_weight 0 mst_edges [] count 0 while heap and count n: w, src, u heapq.heappop(heap) if visited[u]: continue visited[u] True mst_weight w count 1 if src ! -1: mst_edges.append((src, u, w)) for v, nw in graph[u]: if not visited[v]: heapq.heappush(heap, (nw, u, v)) if count ! n: return None, -1 return mst_edges, mst_weight这里有一个关键点堆里可能同时存在同一顶点的多个候选比如点a可能被邻接点b和c分别以不同权重压入堆。弹出时如果该点已经被访问过说明已经有更优的路径先到达了它直接跳过即可。这种“懒删除”策略是堆优化Prim的常见实现方式代码简洁代价是堆里会有少量冗余元素内存占用略高但实际性能依然很好。4.3 Prim 的复杂度分析以及为什么稠密图用朴素版更稳堆优化Prim的时间复杂度是O(m log n)。每一条边最多被压入堆一次另一方向也会被压入所以实际是O(m log n)每次堆操作O(log n)。朴素Prim的复杂度是O(n^2)每轮扫描n个点找最小值总共n轮。在稠密图m接近n^2里O(m log n)其实比O(n^2)更慢因为m log n n^2 log n n^2。这就是为什么很多人说“稠密图用朴素Prim稀疏图用Kruskal或堆优化Prim”。这个结论不是谁拍脑袋定的是复杂度推导出来的。平时刷题时看到n是10^4级别而边是10^7级别优先考虑朴素Prim看到n很大但边很少优先考虑Kruskal。4.4 两个小坑重边和自环Prim实现还有个容易被忽视的坑重边。如果两个顶点之间有多次连接、权重不同堆优化Prim天然能处理——它会把所有边都压入堆最终只保留最小的那条。但朴素Prim用数组存最小距离时如果初始化时直接覆盖而不是取min就可能出错。正确做法是初始化时取dist[v] min(dist[v], w)。自环同理自环边的权重如果比当前dist大不影响但如果不小心用自环覆盖了正常边的距离就会出现“点已经在树里了却还在更新自己距离”这类诡异问题。这些边界情况在做竞赛题时非常常见。我印象里不少题目喜欢在测试数据里塞重边专门钓那些没处理取min的选手。所以写模板时建议养成习惯不管什么方法读边时都加一句dist[a][b] min(dist[a][b], w)一劳永逸。5. 两种算法如何选——决策表与几种边界情况的实战处理5.1 Kruskal 与 Prim 的完整对比很多教材喜欢说“两种算法都能求MST”但实际工程里选错算法可能让程序跑几分钟和跑几秒钟的差别。我把关键差异整理成了一张表对比维度KruskalPrim堆优化Prim朴素核心思想按边排序贪心选边从点出发切分扩展同左主要数据结构并查集优先队列堆数组维护最小距离时间复杂度O(m log m)O(m log n)O(n^2)适合场景稀疏图m接近n稀疏图/中等稠密图m接近n^2实现难度较低中等较低是否需要邻接表只需边集需要邻接表需要邻接矩阵或邻接表处理重边排序后自然处理堆里重复入跳过早需显式取min处理图不连通边数不足检测count ! n 检测检查dist无穷大直观结论如果m很大约n^2级别用朴素Prim如果m接近n用Kruskal如果n和m都是10^5级别堆优化Prim和Kruskal都行但Kruskal代码更短、更好调试。我自己的实际经验刷题和面试时Kruskal往往比Prim更快写对因为并查集模板很固定排序也简单。Prim如果要用堆优化还要注意堆里冗余元素的处理容易在边界条件上翻车。所以如果题目没有明确要求用哪种我默认优先写Kruskal。但这不意味着Prim可以不学有些题的图是“几乎完全图”比如任意两点都有边这时Kruskal要排序千万条边而朴素Prim复杂度更优用对算法能省不少时间。5.2 图不连通时的处理MST有一个前提图必须连通。实际数据却不一定讲道理。Kruskal实现里我判断len(mst_edges) ! n - 1作为不连通标志这利用了“n个顶点的树恰好有n-1条边”的性质。如果图有多个连通分量Kruskal只能生成一个分量的生成森林边数必然少于n-1。Prim实现里则用count ! n判断因为如果某个点始终无法被访问到说明它和起点不在同一个连通分量里。还有一种情况是一开始图就不是连通的但题目不保证。这时Kruskal返回None调用方需要处理“没有MST”的情形。竞赛里常见的是输出“impossible”或者-1。很多人写了Kruskal就把这个判断漏了结果遇到不连通数据直接数组越界或者计算出错误答案排查时很费劲。5.3 负权边能让 MST 失效吗一个比较常见的问题是图里有负权边MST会受影响吗答案是不会。最小生成树只关心总权重最小负权边只要不形成环、能降总权重就可以正常选。所有基于切分性质和环路性质的证明都不要求权值非负Prim和Kruskal都能处理负权边。这里和最短路径的Dijkstra算法不太一样。Dijkstra遇到负权边会失效但MST算法不会因为MST不需要维护“从起点到某点的距离”这种累计量它只比较单条边的权重。初学者容易把这两个问题混在一起把Dijkstra的局限错误地迁移到MST上。其实只要记住MST问的是“树的权重总和”Dijkstra问的是“路径的权重总和”后者受负权影响前者不受。6. 从“求最小”到“求次小”再到真实工程场景6.1 最大生成树和次小生成树MST的变体不少这里说两个最常见的。第一个是最大生成树。直接把所有边权重取负号再跑一遍Kruskal或Prim算出来的就是最大生成树。因为排序时取负号等价于按原权值从大到小排整个贪心逻辑不变。比如在“要最大化连接质量”的场景比如带宽要求最大生成树很有用。第二个是次小生成树。次小生成树是权重第二小的生成树它可以和MST相同也可以不同。求法比较经典先求出MST然后枚举每一条不属于MST的边e(u, v)如果把e加进MST会形成一个环在环上找一条除e外最大的边f它在MST里用e替换f得到一个新生成树权重是MST总权重 - weight(f) weight(e)。对所有非树边做这种替换取权重最小且大于MST权重的结果就是严格次小生成树。实现这个思路时找“环上最大的边”需要树上倍增等技巧代码量比较大但思路本身值得理解。它和“最小生成树唯一性”的问题也相关——如果每一条非树边替换后的权重都大于等于MST权重那么MST唯一如果存在某条非树边替换后权重等于MST权重说明MST不唯一。有些面试题喜欢围绕“MST是否唯一”做文章本质上就是在考这个替换逻辑。6.2 最小生成树在聚类和图像分割里的应用MST不只是算法题。在无监督学习里有一种叫单链接聚类single-linkage clustering的方法本质就是MST。思路是把高维数据点看成图的顶点点与点的距离看成边的权重构造出MST。然后从总权重大的边开始剪剪断几条就把数据分成了几个簇。因为MST保留了“最紧密的连接”剪掉大的边相当于断开最不相似的连接剩下的连通块就是聚类结果。图像分割里也有类似用法。把每个像素看成顶点相邻像素的亮度差看成边权构造MST然后根据亮度差阈值剪断某些边得到分割区域。这类方法叫基于图割的分割当年在计算机视觉里火过一阵。我第一次看到MST用在图像领域时还挺惊讶因为它看起来就是个离散数学工具但实际可以用来处理连续图像数据。6.3 网线布线时的一个实战教训回到开头那个布线项目。我当时用Kruskal算完最小生成树让施工队按方案布线结果发现有个致命问题MST保证了总成本最低但它完全不考虑“延迟”。MST里两个点之间的通信路径可能绕很远实际办公场景里工位A和工位B之间可能经常要传大文件绕远路会导致网络延迟高体验差。这个问题让我意识到MST只是一种“成本约束下的最优解”但工程里往往还有性能约束、可靠性约束和实用性约束。实践中更合理的设计是先保证MST作为骨架再根据重要节点之间的通信需求额外地加几条关键直连链路形成一个“MST少量冗余边”的混合拓扑。这个例子说明算法给出的是数学最优解是否等于工程最优解要结合场景判断不能盲目套用。不过话说回来正因为MST能用极低的算法复杂度给出一套“足够好”的初始方案它在工程规划阶段仍然非常实用。哪怕最终拓扑要调整MST也是一个极佳的起点。7. 我踩过的几个坑和给你避坑建议写到这里MST的主要内容基本讲完了最后分享几个我实际编码时踩过的坑。第一个坑是Kruskal里忘了处理“图不连通”的情况。我早期比赛时有一次把n个点、m条边的数据测了前几组都对到后面有一组图本身不连通程序直接返回了一个“边数不足”的数组后续逻辑全崩。后来我写Kruskal时总是会在循环结束后检查len(mst_edges) n - 1不满足就直接返回异常或-1再也没犯过同样的错误。第二个坑是重边。Prim的朴素实现里如果初始化dist数组时不取min重边会导致dist被覆盖成较大值导致算法选了错误的边。这个问题最隐蔽因为小数据里重边不多跑起来也没报错就是答案不对。现在我在处理图的输入时只要涉及“求两个点之间的最小距离/最小边权”这类需求一律写min这已经成了肌肉记忆。第三个坑是堆优化Prim里忘了跳过已访问节点。如果弹出堆顶时发现该点已经在MST里就直接continue否则会把同一个点重复加入MST导致结果含环或者边数超过n-1。这个问题我在手写代码时遇过好几次每次都想骂自己“怎么又忘了”。其实原因很简单同一顶点可能被多个邻居以不同权重压入堆堆里同时存在多条候选弹出顺序取决于权重后弹出的必然是无效的必须跳过。第四个是负权边的问题。虽然我说MST算法能处理负权边但有个细节如果图里有负权边且允许“必须全选”MST仍是正确的但如果你在“剪边”思路里理解MST可能会被负权边绕晕。记住一条简单的判断标准最小生成树选的是“哪些边连成树”不是“从起点到某点的距离”所以负权不影响。最后给大家一个练手建议想真正理解MST别只看代码拿一张纸画一个带权重的图手动模拟一遍Kruskal的选边过程。我当年就是这么干的模拟了三张图之后再理解Prim就顺畅多了。最小生成树是个特别经典的贪心算法思路一旦通了后面学习其它图论算法比如最短路、网络流也能触类旁通值得多花点时间把它弄扎实。