如果你正在学数据结构或者准备考研复习到了“图”这一章估计绕不开最小生成树。这个知识点在教材里通常放在图的后半部分前面刚讲完DFS、BFS、拓扑排序紧接着就是最小生成树和最短路径很多人在这个节点开始犯迷糊。其实最小生成树解决的是非常朴素的问题怎么在保证所有节点连通的前提下让总的连接成本最低。放在带权连通图里就是寻找一棵包含全部顶点、且各边权值总和最小的生成树。我也走过一段弯路以为只要记住Kruskal排序选边、Prim扩张集合就算学会了真到写代码和做实验的时候才发现光是“为什么每次选最小边不会出错”“为什么Kruskal要并查集而不是一个visited数组”这两个问题就够我琢磨很久。所以这篇内容是按照我自己的学习顺序来写的先搞懂它在解决什么问题再拆解算法为什么成立然后用具体图手动推一遍最后给出可以直接跑的代码和几个高频坑点。无论是期末复习、考研还是工作中需要用图模型做网络规划这篇都适合。1. 先搞清楚最小生成树到底解决的是哪类问题1.1 从一个布线场景说起假设要在一个园区里布设光纤园区里分散着6栋楼楼和楼之间拉光缆的成本不一样。有的距离近、地质条件好几千块就能搞定有的要跨马路、绕过管道成本直接翻倍。现在你只有两个目标每栋楼都要能通过光纤网络联通不能有楼孤立总造价尽量低。这个场景放到图论里楼就是顶点楼与楼之间如果允许拉光缆就是一条带权边权重就是成本。那你最后要选的不是一个“连通得挺密”的网络而是一棵刚好把所有顶点串起来、又没有任何多余回路的树。因为回路意味着冗余一旦出现回路环里的某条边删掉后连通性并不受影响那条边就是白花钱。这个“去掉冗余、保留最低成本连通方式”的结果就是最小生成树。名字听起来吓人本质却是“花最少的钱把点全部连起来”。1.2 生成树、连通图、最小生成树的准确定义先复习几个基础定义否则后面讨论容易绕。连通图任意两个顶点之间都存在路径的图。也就是说从任何一个点出发都能走到图的任何另一个点。生成树一个连通图的生成子图它包含图里全部顶点同时又是一棵树。所谓树就是连通且无环。所以生成树可以理解成“从原图里挑出一些边让所有点依然连通但边数正好是顶点数减一”。最小生成树Minimum Spanning TreeMST在一张带权连通图里所有生成树中边权总和最小的那棵。一个很关键的直觉是n个顶点如果要连通至少需要n-1条边。少于这个数量必然有点孤立多于这个数量必然出现回路。而任何一棵n个顶点的树边数恰好是n-1条。所以最小生成树搜索范围其实非常明确在一个可能有很多条边的带权图里选出n-1条边让它们不构成环而且把全部顶点连通最后权值总和最小。这个“n-1条边”的边界条件在后面写代码判断退出条件时非常有用。1.3 为什么说最小生成树是“高效连通”的最优解把“高效”拆开看有两点第一边数效率高。n个顶点的连通图至少需要n-1条边最小生成树正好就停在n-1条边上不多选一条多余边。所以在“保证连通”这件事上它以最少的边数完成了目标。第二成本效率高。如果在满足“n-1条边且无环”的前提下还能做到总权值最小就说明你在所有可行的“最小骨架”里挑了最便宜的那个。这比单纯找一棵生成树复杂得多因为n个顶点的完全图里可能的生成树数量已经大到指数级别不可能穷举。所以最小生成树并不是一个抽象概念它就是通信网络、供水管网、电网规划这类场景里最直接的计算模型。工程上两点之间成本最小的路径可能很重要但很多规划类问题第一步都是先算出一棵最小生成树作为主骨架。2. 两个贪心算法的原理与数据结构依赖2.1 贪心为什么在这里是对的切分定理与环性质最小生成树领域有两个经典算法——Kruskal和Prim通常归在“贪心算法”阵营里。但很多人对贪心有误解以为贪心就是“每次无脑选当前最优反正局部最优能推出全局最优”。这句话放在很多问题是错的可在最小生成树问题上偏偏成立。为什么关键在两条底层性质。第一条叫切分定理把一张连通图的顶点集合切成两部分一部分是S一部分是V-S那么横跨这两个部分的边里权值最小的一条一定属于某棵最小生成树。你可以想象成拿一把刀把图切成了两堆连接两堆的边都是“桥”最短的那座桥值得优先搭。理由不复杂如果某棵最小生成树没有选这座最短桥那树里一定也横跨了另一个切口来保证两堆点连通把那座更长的桥换掉连通性不会破坏总权值反而更小或不变。第二条叫环性质如果一个环里某条边是环上唯一最重的边那它一定不会出现在任意最小生成树里。因为生成树不能含环环里总要放弃某条边那自然优先放弃最贵的那条。最小生成树问题能贪心本质上是因为这两个性质保证局部做“最小替换”不会把结果带偏。这和背包问题里“只按单位重量贪心却不成立”形成了鲜明对比。理解这一点比单纯背步骤有用得多很多面试追问都在这里。2.2 Kruskal算法从小到大挑边靠并查集避环Kruskal的思路一句话把所有边按权重从小到大排序尽量挑小边但前提是别构成环。具体流程是把图的边全部拿出来按权值升序排初始化一个并查集让每个顶点各自成为一个集合依次遍历排序后的边对边(u, v)如果u和v当前不在同一个集合里说明选这条边不会成环选它并把u、v合并到同一个集合如果已经在同一个集合说明这条边会导致环直接跳过当已选边数达到n-1算法结束。这里边权排序是典型排序问题而“是否成环”的判断则必须依赖并查集。并查集在Kruskal里的作用就是实时维护“当前已经连成了哪些连通块”。Kruskal的特点是不管顶点是从哪个点开始的它关注的是全局最小的边来不来。所以对边集数据结构友好代码很容易写。2.3 Prim算法顶点集合扩张靠优先队列找最小横跨边Prim的思路和Kruskal完全不同它从一个起点出发像“长草”一样不断扩大一棵树。具体流程是选任意一个顶点作为初始集合S在横跨集合S和集合外顶点的所有边里找一条权值最小的边把这条边连接的外部顶点加入S重复第2步直到所有顶点都进入S。注意Kruskal选的是“原图当前最小的任意边”Prim选的是“当前树边界上最小的连接边”。这是一个关键区别。在数据结构上Prim自然适合用邻接表或邻接矩阵存图。如果每次“找最小横跨边”都暴力扫描所有外部顶点复杂度是O(V²)如果借助二叉堆优先队列来维护候选边典型复杂度可以降到O(E log V)。很多教材在讲Prim时用“蓝白点”来比喻蓝点是已经进入树的白点是还没进入的。其实不必记颜色抓住“已选集合S扩张”这个核心就够了。2.4 Prim和Kruskal到底该怎么选很多初学者会有疑问两个算法都能求最小生成树考试里两种都要求掌握那实际工程里到底选哪个我的建议是看图的存储方式和稠密程度Kruskal的复杂度主要取决于边数E适合稀疏图。稀疏图指的是边数远小于V²比如V1万、E5万这种图用邻接表存Kruskal排序E条边效率很理想。Prim朴素实现的复杂度是O(V²)当图是稠密图比如E接近V²时用邻接矩阵存图暴力维护最小横跨边反而简单稳定而且不依赖排序。Prim如果用邻接表加二叉堆复杂度O(E log V)在中等链路上比较不错但要注意堆里可能会有重复候选边代码要配合visited数组去重。所以别神话某一个算法。考试题里如果给出邻接矩阵V只有几百朴素Prim写起来最顺手如果给出的是边列表并且顶点很多边很少Kruskal几乎永远是优选。3. 手推一遍用6个顶点把两种算法跑明白3.1 准备一张带权连通图只看伪代码很容易觉得自己懂了真到手动推的时候才会发现细节问题。下面用一张6顶点、10条边的带权连通图走一遍完整过程。顶点设为A、B、C、D、E、F边的权重如下边权重A-B4A-C2B-C1B-D5C-D3C-E6D-E2D-F7E-F8你可以自己在纸上画一下。这张图是连通的任意顶点都能到达其它顶点所以一定存在生成树也一定存在最小生成树。3.2 Kruskal推演全记录第一步把10条边按权值升序排列。排序后结果是顺序边权重1B-C12A-C23D-E24C-D35A-B46B-D57C-E68D-F79E-F8然后初始化并查集每个点单独一个集合。选边1B-C权重1。B和C在不同的集合选入合并B、C。已选边数1。选边2A-C权重2。A和C在不同的集合选入合并A与{B,C}。已选边数2。选边3D-E权重2。D和E在不同的集合选入合并D、E。已选边数3。选边4C-D权重3。C所在集合包含{A,B,C}D所在集合包含{D,E}是两个不同集合选入相当于把两个连通块合并成一个大块。已选边数4。选边5A-B权重4。此时A和B已经在同一个连通块里如果选这条边A-B-C-D-E这个结构里会立刻出现环A-B-C-A。所以跳过。选边6B-D权重5。B和D也已经在一个连通块里选上会成环跳过。选边7C-E权重6。C和E也已经在同一个连通块里跳过。选边8D-F权重7。D所在集合包含所有A到E的顶点F还是独立点选入不会成环而且正好让F接入网络。已选边数5达到n-15算法结束。所以Kruskal选出的边为B-C、A-C、D-E、C-D、D-F总权重是1223715。3.3 Prim推演全记录这次从A点出发初始已选集合S{A}。第一步看所有从S连到外部的边A-B权重4A-C权重2。最小的是A-C选它把C放入S。总权重2。第二步S{A,C}。连接S和外部顶点的边有A-B权重4、C-B权重1、C-D权重3、C-E权重6。最小的是C-B权重1。选B入S。总权重3。第三步S{A,B,C}。外部顶点只剩D、E、F。横跨边有B-D权重5、C-D权重3、C-E权重6。最小的是C-D权重3。选D入S。总权重6。第四步S{A,B,C,D}。横跨边有D-E权重2、D-F权重7、C-E权重6。最小的是D-E权重2。选E入S。总权重8。第五步S{A,B,C,D,E}。外部只剩F。横跨边有D-F权重7、E-F权重8。最小的是D-F权重7。选F入S。总权重15。此时全部顶点都已加入算法结束。Prim选出的边是A-C、B-C、C-D、D-E、D-F总权重同样是15。3.4 选出的边会一样吗在上面的例子中Kruskal和Prim最终选出的边集合其实是一样的只是加入顺序不同。这并不意味着两个算法任何时候都选出一模一样的边。当图中存在相同权重的边时最小生成树可能不唯一。比如两条边权重都是2并且都满足不构成环的条件Kruskal先扫到哪条就会选哪条Prim则取决于当前已选集合里的横跨边中哪条最小以及堆中的优先级。如果边权完全不一致通常能确定一棵唯一的最小生成树一旦有权值相等的边就可能出现多种选择但只要算法正确所有方案的总权值一定相同都是全局最小。平时复习时要养成推理习惯选边时先问自己“会不会成环”。这个习惯比记忆过程更重要它可以让你在复杂甚至混乱的图上也不会走错。4. 代码落地两套可以直接抄的实现4.1 Kruskal实现并查集要写好Kruskal代码本身的循环逻辑不复杂真正决定正确性和性能的是并查集。并查集如果不带路径压缩或者只带路径压缩却不带按秩合并在极端数据下可能退化成一条链效率会很差。下面的实现用的是“路径压缩 按秩合并”find的过程把树的高度尽量压低union的过程把矮树挂到高树下面整体复杂度可以认为接近常数。class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [0] * 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): ra self.find(a) rb self.find(b) if ra rb: return False if self.rank[ra] self.rank[rb]: ra, rb rb, ra self.parent[rb] ra if self.rank[ra] self.rank[rb]: self.rank[ra] 1 return True def kruskal(n, edges): # edges: [(u, v, weight)] edges.sort(keylambda x: x[2]) dsu DSU(n) mst_edges [] total 0 for u, v, w in edges: if dsu.union(u, v): mst_edges.append((u, v, w)) total w if len(mst_edges) n - 1: break return total, mst_edges测试上面的例子时只要把顶点映射成0到5的数字传进去就能得到总权重15。写代码时有个小点值得注意union函数返回布尔值来表示这次合并是否成功。如果两个点已经在同一集合说明边会造成环返回False这样外层循环直接跳过比先find再union要少写一两次调用逻辑也统一。4.2 Prim实现优先队列的正确打开方式Prim如果用邻接表加优先队列代码写起来最接近“从集合边界上不断取最小边”的思路。不过很多人在写的时候容易漏掉visited去重。因为一条外部顶点可能通过多个已入树顶点被反复放入堆如果不对已入树的顶点做标记算法会重复处理逻辑会乱复杂度也会增加。import heapq def prim(n, adj): # adj: 邻接表, adj[u] [(v, weight)] visited [False] * n min_heap [(0, 0, -1)] # (weight, vertex, from_vertex) total 0 mst_edges [] while min_heap: w, u, src heapq.heappop(min_heap) if visited[u]: continue visited[u] True if src ! -1: mst_edges.append((src, u, w)) total w for v, w2 in adj[u]: if not visited[v]: heapq.heappush(min_heap, (w2, v, u)) return total, mst_edges初始把(0, 0, -1)放进去意思是起点0入树花费0。弹出起点后把它所有邻边入堆。以后每次弹出最小候选边如果那个顶点还没访问过就把它纳入树中同时更新邻接边的候选。堆中可能出现早先通过别的顶点放进去的“旧边”但因为起点目标点已经被visit成True下次弹出时会被continue跳过不会影响结果。Prim如果使用邻接矩阵可以省掉优先队列每次暴力扫描比较所有未访问点的距离数组。写法虽然朴素但在顶点数只有几百的题目里非常稳少很多堆操作上的麻烦。我当时写邻接矩阵版Prim时一个容易忽略的细节是每次选出一个新点后要更新它到所有未访问点的最短距离而不是只考虑和当前集合里“最后一个点”的连边。简化的常见写法是用数组dis[v]表示外部点v到已选集合的最小边权每加入一个新点u就把dis[v]更新为min(dis[v], g[u][v])。这才是Prim正确的迭代逻辑。4.3 复杂度和工程取舍算法核心数据结构时间复杂度空间复杂度适合场景Kruskal边集排序 并查集O(E log E)O(E)稀疏图Prim朴素邻接矩阵 距离数组O(V^2)O(V^2)稠密图、顶点少Prim 二叉堆邻接表 优先队列O(E log V)O(V E)中大图通用这里有一个很多教材不细讲但工程里很实际的点Kruskal对图的存储方式很宽容只需要把所有边拿出来排序不需要特意建立邻接表Prim的堆优化则必须要邻接表。因此如果你拿到的数据本身就是“边列表”做Kruskal几乎零成本如果项目里已经用邻接矩阵存图而且点的规模不大朴素Prim根本不需要额外建边列表。还有复杂度符号背后的问题O(E log E)里的排序在大数据量下是主要瓶颈Prim朴素实现不排序但每轮要找最小距离点做V轮每轮扫描V个点所以是V²。当V从1000涨到10000时V²部分涨得非常快这也是稠密图之外选择堆优化的原因。5. 实际使用中高频踩坑点与排查思路5.1 图本身不连通怎么办跑出最小生成森林最小生成树定义要求原图是连通图。考试题一般只会给合法数据但自己做项目或写练习题时图未必连通。这时候如果直接跑Kruskal它的退出条件“已选边数 n-1”永远不会满足但并不会崩溃代码跑完后只会选到“每个连通分量各自生成树”的边总边数等于n减去连通分量个数。比如一个图分成三个互不相连的块最后Kruskal选出的边数就是n-3其实是求出了一片最小生成森林也就是每个连通分量各自的最小生成树拼在一起。Prim如果只从任意一点出发则只能访问起点所在连通分量的顶点另一部分顶点根本不会被扫描到。所以工程中建议先做一次DFS/BFS统计连通分量确认输入是连通图或者直接改Kruskal因为它在非连通图上也能稳定返回森林结果不需要额外判断。我自己的习惯是Kruskal写完后顺便统计一下选了多少条边如果少于n-1就提示用户“输入图不连通”。5.2 重边、自环和负权边怎么处理重边完全不用怕算法天然会选权重较小的那条。如果你在Kruskal排序里把两条同端点边放一起检查到第一条如果选了第二条在判断并查集时大概率会因为两个端点已经连通而被跳过如果第一条没选第二条权值更大更不会影响结果。Prim也是同理候选边里小的自然会先弹出。自环要主动忽略。自环的两端是同一个顶点在Kruskal里find(u)和find(v)当然相等并查集会直接拒绝在Prim的邻接表里如果建图时写了u-u的边入堆后当这个顶点已被访问时会跳过不会真正被选入。可有些代码在起点初始化时把自环也push进去可能导致弹出的边虽然不选但白白增加堆的规模。建议建图时直接跳过uv的边。负权边则不需要额外处理。最小生成树要求是生成一棵树不能有环无论边权正负都成立。负权值如果很大算法会尽量选它但依然要避环。这和最短路径里的负权环问题是两码事别混为一谈。5.3 为什么不能用visited数组代替并查集判环这是我在调试Kruskal时最容易犯的错误也是面试里高频追问。有同学会想只要这条边的两个端点都还没访问过是不是就能选换一种思路把所有顶点都打上visited标记不也可以吗实际上不行。Kruskal在选边的过程中整个图可能同时存在多个独立的连通块。一条边的两个端点可能都已经被访问过但它们分属两个不同连通块此时连接它们的边恰恰是合并两个块的最优边必须选如果简单跳过最后可能会丢掉需要的那条边。举个例子假设一串连通块A-B和C-D各自内部已经通过前面更小的边连通这时遇到边A-C虽然A和C都已经访问过但A-C把两个分块拼成了一个更大的整体既不会形成环又合法。所以Kruskal判环必须用并查集判断的是“两个端点当前是否在同一集合”而不是“是否被访问过”。Prim可以只用visited数组因为它维护的始终是一个连续扩大的集合一旦发现外部顶点已经访问就说明加入它会成环这个判断对Prim是够用的。理解两者差异比背结论更能避免踩坑。5.4 相等权重会让最小生成树结果不唯一在推演那张图时如果两条最小边权重相同比如排序时D-E和A-C都是2Kruskal先扫到哪条取决于排序算法的稳定性以及原始边的顺序但最后总权重不会变。一个非常常见的考试题会故意构造多条权重相等的边问你最小生成树是否唯一。判断唯一性的方法不是跑一次算法看结果而是检查整个选边过程里有没有“权重相等且可以被替换的边”。严谨一点的思路是如果一条边是某个环上唯一最重的边它一定不被任何MST包含如果一条边只是“环上最重之一”则可能存在不包含该边的另一棵MST。这个点初学阶段可以只做了解遇到专门题目再深入。5.5 面试和考试里常见的问题方向总结一下我遇到过的几个高频考察角度最小生成树边数一定是n-1为什么可以回顾树的定义也可以通过反证法说明边多必成环边少必不连通。Kruskal和Prim各自使用什么数据结构为什么那样选这题问你并查集和优先队列的动机。输入图很大V到10万级E到20万级选哪个算法多数情况下Kruskal更合适因为稀疏图的瓶颈主要是排序边而Prim朴素O(V²)会直接超时。给你两棵生成树如何判断是不是最小不能只判断边数还要看“是否存在一条边能被另一条边替换并减少总权值”这正好又回到切分定理和环性质上。我这两年带朋友调最小生成树代码发现大部分bug不是算法理解错了而是并查集写得不对或者堆优化忘记标记visited。遇到结果偏大先查是不是少选了几条边或跳错了正确边遇到死循环优先怀疑堆里旧边没有跳过其次再怀疑邻接表建图出了问题。这些经验比任何技巧都实用自己动手跑一遍才能体会。最后再说一点个人体会最小生成树的代码量其实不大难就难在你要相信“贪心选边”这条路真的成立。如果你学的时候也卡在原理上建议拿一张小的手绘图像我在第3节那样一步步推演两轮比直接刷十道题都管用。后续如果想继续扩展可以从次小生成树、Kruskal重构树、最小瓶颈生成树这几个方向入手它们都能由最小生成树衍生出很有意思的结论也能帮你把这块数据结构彻底打牢。
最小生成树详解：Kruskal与Prim算法原理、推演与代码实现
如果你正在学数据结构或者准备考研复习到了“图”这一章估计绕不开最小生成树。这个知识点在教材里通常放在图的后半部分前面刚讲完DFS、BFS、拓扑排序紧接着就是最小生成树和最短路径很多人在这个节点开始犯迷糊。其实最小生成树解决的是非常朴素的问题怎么在保证所有节点连通的前提下让总的连接成本最低。放在带权连通图里就是寻找一棵包含全部顶点、且各边权值总和最小的生成树。我也走过一段弯路以为只要记住Kruskal排序选边、Prim扩张集合就算学会了真到写代码和做实验的时候才发现光是“为什么每次选最小边不会出错”“为什么Kruskal要并查集而不是一个visited数组”这两个问题就够我琢磨很久。所以这篇内容是按照我自己的学习顺序来写的先搞懂它在解决什么问题再拆解算法为什么成立然后用具体图手动推一遍最后给出可以直接跑的代码和几个高频坑点。无论是期末复习、考研还是工作中需要用图模型做网络规划这篇都适合。1. 先搞清楚最小生成树到底解决的是哪类问题1.1 从一个布线场景说起假设要在一个园区里布设光纤园区里分散着6栋楼楼和楼之间拉光缆的成本不一样。有的距离近、地质条件好几千块就能搞定有的要跨马路、绕过管道成本直接翻倍。现在你只有两个目标每栋楼都要能通过光纤网络联通不能有楼孤立总造价尽量低。这个场景放到图论里楼就是顶点楼与楼之间如果允许拉光缆就是一条带权边权重就是成本。那你最后要选的不是一个“连通得挺密”的网络而是一棵刚好把所有顶点串起来、又没有任何多余回路的树。因为回路意味着冗余一旦出现回路环里的某条边删掉后连通性并不受影响那条边就是白花钱。这个“去掉冗余、保留最低成本连通方式”的结果就是最小生成树。名字听起来吓人本质却是“花最少的钱把点全部连起来”。1.2 生成树、连通图、最小生成树的准确定义先复习几个基础定义否则后面讨论容易绕。连通图任意两个顶点之间都存在路径的图。也就是说从任何一个点出发都能走到图的任何另一个点。生成树一个连通图的生成子图它包含图里全部顶点同时又是一棵树。所谓树就是连通且无环。所以生成树可以理解成“从原图里挑出一些边让所有点依然连通但边数正好是顶点数减一”。最小生成树Minimum Spanning TreeMST在一张带权连通图里所有生成树中边权总和最小的那棵。一个很关键的直觉是n个顶点如果要连通至少需要n-1条边。少于这个数量必然有点孤立多于这个数量必然出现回路。而任何一棵n个顶点的树边数恰好是n-1条。所以最小生成树搜索范围其实非常明确在一个可能有很多条边的带权图里选出n-1条边让它们不构成环而且把全部顶点连通最后权值总和最小。这个“n-1条边”的边界条件在后面写代码判断退出条件时非常有用。1.3 为什么说最小生成树是“高效连通”的最优解把“高效”拆开看有两点第一边数效率高。n个顶点的连通图至少需要n-1条边最小生成树正好就停在n-1条边上不多选一条多余边。所以在“保证连通”这件事上它以最少的边数完成了目标。第二成本效率高。如果在满足“n-1条边且无环”的前提下还能做到总权值最小就说明你在所有可行的“最小骨架”里挑了最便宜的那个。这比单纯找一棵生成树复杂得多因为n个顶点的完全图里可能的生成树数量已经大到指数级别不可能穷举。所以最小生成树并不是一个抽象概念它就是通信网络、供水管网、电网规划这类场景里最直接的计算模型。工程上两点之间成本最小的路径可能很重要但很多规划类问题第一步都是先算出一棵最小生成树作为主骨架。2. 两个贪心算法的原理与数据结构依赖2.1 贪心为什么在这里是对的切分定理与环性质最小生成树领域有两个经典算法——Kruskal和Prim通常归在“贪心算法”阵营里。但很多人对贪心有误解以为贪心就是“每次无脑选当前最优反正局部最优能推出全局最优”。这句话放在很多问题是错的可在最小生成树问题上偏偏成立。为什么关键在两条底层性质。第一条叫切分定理把一张连通图的顶点集合切成两部分一部分是S一部分是V-S那么横跨这两个部分的边里权值最小的一条一定属于某棵最小生成树。你可以想象成拿一把刀把图切成了两堆连接两堆的边都是“桥”最短的那座桥值得优先搭。理由不复杂如果某棵最小生成树没有选这座最短桥那树里一定也横跨了另一个切口来保证两堆点连通把那座更长的桥换掉连通性不会破坏总权值反而更小或不变。第二条叫环性质如果一个环里某条边是环上唯一最重的边那它一定不会出现在任意最小生成树里。因为生成树不能含环环里总要放弃某条边那自然优先放弃最贵的那条。最小生成树问题能贪心本质上是因为这两个性质保证局部做“最小替换”不会把结果带偏。这和背包问题里“只按单位重量贪心却不成立”形成了鲜明对比。理解这一点比单纯背步骤有用得多很多面试追问都在这里。2.2 Kruskal算法从小到大挑边靠并查集避环Kruskal的思路一句话把所有边按权重从小到大排序尽量挑小边但前提是别构成环。具体流程是把图的边全部拿出来按权值升序排初始化一个并查集让每个顶点各自成为一个集合依次遍历排序后的边对边(u, v)如果u和v当前不在同一个集合里说明选这条边不会成环选它并把u、v合并到同一个集合如果已经在同一个集合说明这条边会导致环直接跳过当已选边数达到n-1算法结束。这里边权排序是典型排序问题而“是否成环”的判断则必须依赖并查集。并查集在Kruskal里的作用就是实时维护“当前已经连成了哪些连通块”。Kruskal的特点是不管顶点是从哪个点开始的它关注的是全局最小的边来不来。所以对边集数据结构友好代码很容易写。2.3 Prim算法顶点集合扩张靠优先队列找最小横跨边Prim的思路和Kruskal完全不同它从一个起点出发像“长草”一样不断扩大一棵树。具体流程是选任意一个顶点作为初始集合S在横跨集合S和集合外顶点的所有边里找一条权值最小的边把这条边连接的外部顶点加入S重复第2步直到所有顶点都进入S。注意Kruskal选的是“原图当前最小的任意边”Prim选的是“当前树边界上最小的连接边”。这是一个关键区别。在数据结构上Prim自然适合用邻接表或邻接矩阵存图。如果每次“找最小横跨边”都暴力扫描所有外部顶点复杂度是O(V²)如果借助二叉堆优先队列来维护候选边典型复杂度可以降到O(E log V)。很多教材在讲Prim时用“蓝白点”来比喻蓝点是已经进入树的白点是还没进入的。其实不必记颜色抓住“已选集合S扩张”这个核心就够了。2.4 Prim和Kruskal到底该怎么选很多初学者会有疑问两个算法都能求最小生成树考试里两种都要求掌握那实际工程里到底选哪个我的建议是看图的存储方式和稠密程度Kruskal的复杂度主要取决于边数E适合稀疏图。稀疏图指的是边数远小于V²比如V1万、E5万这种图用邻接表存Kruskal排序E条边效率很理想。Prim朴素实现的复杂度是O(V²)当图是稠密图比如E接近V²时用邻接矩阵存图暴力维护最小横跨边反而简单稳定而且不依赖排序。Prim如果用邻接表加二叉堆复杂度O(E log V)在中等链路上比较不错但要注意堆里可能会有重复候选边代码要配合visited数组去重。所以别神话某一个算法。考试题里如果给出邻接矩阵V只有几百朴素Prim写起来最顺手如果给出的是边列表并且顶点很多边很少Kruskal几乎永远是优选。3. 手推一遍用6个顶点把两种算法跑明白3.1 准备一张带权连通图只看伪代码很容易觉得自己懂了真到手动推的时候才会发现细节问题。下面用一张6顶点、10条边的带权连通图走一遍完整过程。顶点设为A、B、C、D、E、F边的权重如下边权重A-B4A-C2B-C1B-D5C-D3C-E6D-E2D-F7E-F8你可以自己在纸上画一下。这张图是连通的任意顶点都能到达其它顶点所以一定存在生成树也一定存在最小生成树。3.2 Kruskal推演全记录第一步把10条边按权值升序排列。排序后结果是顺序边权重1B-C12A-C23D-E24C-D35A-B46B-D57C-E68D-F79E-F8然后初始化并查集每个点单独一个集合。选边1B-C权重1。B和C在不同的集合选入合并B、C。已选边数1。选边2A-C权重2。A和C在不同的集合选入合并A与{B,C}。已选边数2。选边3D-E权重2。D和E在不同的集合选入合并D、E。已选边数3。选边4C-D权重3。C所在集合包含{A,B,C}D所在集合包含{D,E}是两个不同集合选入相当于把两个连通块合并成一个大块。已选边数4。选边5A-B权重4。此时A和B已经在同一个连通块里如果选这条边A-B-C-D-E这个结构里会立刻出现环A-B-C-A。所以跳过。选边6B-D权重5。B和D也已经在一个连通块里选上会成环跳过。选边7C-E权重6。C和E也已经在同一个连通块里跳过。选边8D-F权重7。D所在集合包含所有A到E的顶点F还是独立点选入不会成环而且正好让F接入网络。已选边数5达到n-15算法结束。所以Kruskal选出的边为B-C、A-C、D-E、C-D、D-F总权重是1223715。3.3 Prim推演全记录这次从A点出发初始已选集合S{A}。第一步看所有从S连到外部的边A-B权重4A-C权重2。最小的是A-C选它把C放入S。总权重2。第二步S{A,C}。连接S和外部顶点的边有A-B权重4、C-B权重1、C-D权重3、C-E权重6。最小的是C-B权重1。选B入S。总权重3。第三步S{A,B,C}。外部顶点只剩D、E、F。横跨边有B-D权重5、C-D权重3、C-E权重6。最小的是C-D权重3。选D入S。总权重6。第四步S{A,B,C,D}。横跨边有D-E权重2、D-F权重7、C-E权重6。最小的是D-E权重2。选E入S。总权重8。第五步S{A,B,C,D,E}。外部只剩F。横跨边有D-F权重7、E-F权重8。最小的是D-F权重7。选F入S。总权重15。此时全部顶点都已加入算法结束。Prim选出的边是A-C、B-C、C-D、D-E、D-F总权重同样是15。3.4 选出的边会一样吗在上面的例子中Kruskal和Prim最终选出的边集合其实是一样的只是加入顺序不同。这并不意味着两个算法任何时候都选出一模一样的边。当图中存在相同权重的边时最小生成树可能不唯一。比如两条边权重都是2并且都满足不构成环的条件Kruskal先扫到哪条就会选哪条Prim则取决于当前已选集合里的横跨边中哪条最小以及堆中的优先级。如果边权完全不一致通常能确定一棵唯一的最小生成树一旦有权值相等的边就可能出现多种选择但只要算法正确所有方案的总权值一定相同都是全局最小。平时复习时要养成推理习惯选边时先问自己“会不会成环”。这个习惯比记忆过程更重要它可以让你在复杂甚至混乱的图上也不会走错。4. 代码落地两套可以直接抄的实现4.1 Kruskal实现并查集要写好Kruskal代码本身的循环逻辑不复杂真正决定正确性和性能的是并查集。并查集如果不带路径压缩或者只带路径压缩却不带按秩合并在极端数据下可能退化成一条链效率会很差。下面的实现用的是“路径压缩 按秩合并”find的过程把树的高度尽量压低union的过程把矮树挂到高树下面整体复杂度可以认为接近常数。class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [0] * 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): ra self.find(a) rb self.find(b) if ra rb: return False if self.rank[ra] self.rank[rb]: ra, rb rb, ra self.parent[rb] ra if self.rank[ra] self.rank[rb]: self.rank[ra] 1 return True def kruskal(n, edges): # edges: [(u, v, weight)] edges.sort(keylambda x: x[2]) dsu DSU(n) mst_edges [] total 0 for u, v, w in edges: if dsu.union(u, v): mst_edges.append((u, v, w)) total w if len(mst_edges) n - 1: break return total, mst_edges测试上面的例子时只要把顶点映射成0到5的数字传进去就能得到总权重15。写代码时有个小点值得注意union函数返回布尔值来表示这次合并是否成功。如果两个点已经在同一集合说明边会造成环返回False这样外层循环直接跳过比先find再union要少写一两次调用逻辑也统一。4.2 Prim实现优先队列的正确打开方式Prim如果用邻接表加优先队列代码写起来最接近“从集合边界上不断取最小边”的思路。不过很多人在写的时候容易漏掉visited去重。因为一条外部顶点可能通过多个已入树顶点被反复放入堆如果不对已入树的顶点做标记算法会重复处理逻辑会乱复杂度也会增加。import heapq def prim(n, adj): # adj: 邻接表, adj[u] [(v, weight)] visited [False] * n min_heap [(0, 0, -1)] # (weight, vertex, from_vertex) total 0 mst_edges [] while min_heap: w, u, src heapq.heappop(min_heap) if visited[u]: continue visited[u] True if src ! -1: mst_edges.append((src, u, w)) total w for v, w2 in adj[u]: if not visited[v]: heapq.heappush(min_heap, (w2, v, u)) return total, mst_edges初始把(0, 0, -1)放进去意思是起点0入树花费0。弹出起点后把它所有邻边入堆。以后每次弹出最小候选边如果那个顶点还没访问过就把它纳入树中同时更新邻接边的候选。堆中可能出现早先通过别的顶点放进去的“旧边”但因为起点目标点已经被visit成True下次弹出时会被continue跳过不会影响结果。Prim如果使用邻接矩阵可以省掉优先队列每次暴力扫描比较所有未访问点的距离数组。写法虽然朴素但在顶点数只有几百的题目里非常稳少很多堆操作上的麻烦。我当时写邻接矩阵版Prim时一个容易忽略的细节是每次选出一个新点后要更新它到所有未访问点的最短距离而不是只考虑和当前集合里“最后一个点”的连边。简化的常见写法是用数组dis[v]表示外部点v到已选集合的最小边权每加入一个新点u就把dis[v]更新为min(dis[v], g[u][v])。这才是Prim正确的迭代逻辑。4.3 复杂度和工程取舍算法核心数据结构时间复杂度空间复杂度适合场景Kruskal边集排序 并查集O(E log E)O(E)稀疏图Prim朴素邻接矩阵 距离数组O(V^2)O(V^2)稠密图、顶点少Prim 二叉堆邻接表 优先队列O(E log V)O(V E)中大图通用这里有一个很多教材不细讲但工程里很实际的点Kruskal对图的存储方式很宽容只需要把所有边拿出来排序不需要特意建立邻接表Prim的堆优化则必须要邻接表。因此如果你拿到的数据本身就是“边列表”做Kruskal几乎零成本如果项目里已经用邻接矩阵存图而且点的规模不大朴素Prim根本不需要额外建边列表。还有复杂度符号背后的问题O(E log E)里的排序在大数据量下是主要瓶颈Prim朴素实现不排序但每轮要找最小距离点做V轮每轮扫描V个点所以是V²。当V从1000涨到10000时V²部分涨得非常快这也是稠密图之外选择堆优化的原因。5. 实际使用中高频踩坑点与排查思路5.1 图本身不连通怎么办跑出最小生成森林最小生成树定义要求原图是连通图。考试题一般只会给合法数据但自己做项目或写练习题时图未必连通。这时候如果直接跑Kruskal它的退出条件“已选边数 n-1”永远不会满足但并不会崩溃代码跑完后只会选到“每个连通分量各自生成树”的边总边数等于n减去连通分量个数。比如一个图分成三个互不相连的块最后Kruskal选出的边数就是n-3其实是求出了一片最小生成森林也就是每个连通分量各自的最小生成树拼在一起。Prim如果只从任意一点出发则只能访问起点所在连通分量的顶点另一部分顶点根本不会被扫描到。所以工程中建议先做一次DFS/BFS统计连通分量确认输入是连通图或者直接改Kruskal因为它在非连通图上也能稳定返回森林结果不需要额外判断。我自己的习惯是Kruskal写完后顺便统计一下选了多少条边如果少于n-1就提示用户“输入图不连通”。5.2 重边、自环和负权边怎么处理重边完全不用怕算法天然会选权重较小的那条。如果你在Kruskal排序里把两条同端点边放一起检查到第一条如果选了第二条在判断并查集时大概率会因为两个端点已经连通而被跳过如果第一条没选第二条权值更大更不会影响结果。Prim也是同理候选边里小的自然会先弹出。自环要主动忽略。自环的两端是同一个顶点在Kruskal里find(u)和find(v)当然相等并查集会直接拒绝在Prim的邻接表里如果建图时写了u-u的边入堆后当这个顶点已被访问时会跳过不会真正被选入。可有些代码在起点初始化时把自环也push进去可能导致弹出的边虽然不选但白白增加堆的规模。建议建图时直接跳过uv的边。负权边则不需要额外处理。最小生成树要求是生成一棵树不能有环无论边权正负都成立。负权值如果很大算法会尽量选它但依然要避环。这和最短路径里的负权环问题是两码事别混为一谈。5.3 为什么不能用visited数组代替并查集判环这是我在调试Kruskal时最容易犯的错误也是面试里高频追问。有同学会想只要这条边的两个端点都还没访问过是不是就能选换一种思路把所有顶点都打上visited标记不也可以吗实际上不行。Kruskal在选边的过程中整个图可能同时存在多个独立的连通块。一条边的两个端点可能都已经被访问过但它们分属两个不同连通块此时连接它们的边恰恰是合并两个块的最优边必须选如果简单跳过最后可能会丢掉需要的那条边。举个例子假设一串连通块A-B和C-D各自内部已经通过前面更小的边连通这时遇到边A-C虽然A和C都已经访问过但A-C把两个分块拼成了一个更大的整体既不会形成环又合法。所以Kruskal判环必须用并查集判断的是“两个端点当前是否在同一集合”而不是“是否被访问过”。Prim可以只用visited数组因为它维护的始终是一个连续扩大的集合一旦发现外部顶点已经访问就说明加入它会成环这个判断对Prim是够用的。理解两者差异比背结论更能避免踩坑。5.4 相等权重会让最小生成树结果不唯一在推演那张图时如果两条最小边权重相同比如排序时D-E和A-C都是2Kruskal先扫到哪条取决于排序算法的稳定性以及原始边的顺序但最后总权重不会变。一个非常常见的考试题会故意构造多条权重相等的边问你最小生成树是否唯一。判断唯一性的方法不是跑一次算法看结果而是检查整个选边过程里有没有“权重相等且可以被替换的边”。严谨一点的思路是如果一条边是某个环上唯一最重的边它一定不被任何MST包含如果一条边只是“环上最重之一”则可能存在不包含该边的另一棵MST。这个点初学阶段可以只做了解遇到专门题目再深入。5.5 面试和考试里常见的问题方向总结一下我遇到过的几个高频考察角度最小生成树边数一定是n-1为什么可以回顾树的定义也可以通过反证法说明边多必成环边少必不连通。Kruskal和Prim各自使用什么数据结构为什么那样选这题问你并查集和优先队列的动机。输入图很大V到10万级E到20万级选哪个算法多数情况下Kruskal更合适因为稀疏图的瓶颈主要是排序边而Prim朴素O(V²)会直接超时。给你两棵生成树如何判断是不是最小不能只判断边数还要看“是否存在一条边能被另一条边替换并减少总权值”这正好又回到切分定理和环性质上。我这两年带朋友调最小生成树代码发现大部分bug不是算法理解错了而是并查集写得不对或者堆优化忘记标记visited。遇到结果偏大先查是不是少选了几条边或跳错了正确边遇到死循环优先怀疑堆里旧边没有跳过其次再怀疑邻接表建图出了问题。这些经验比任何技巧都实用自己动手跑一遍才能体会。最后再说一点个人体会最小生成树的代码量其实不大难就难在你要相信“贪心选边”这条路真的成立。如果你学的时候也卡在原理上建议拿一张小的手绘图像我在第3节那样一步步推演两轮比直接刷十道题都管用。后续如果想继续扩展可以从次小生成树、Kruskal重构树、最小瓶颈生成树这几个方向入手它们都能由最小生成树衍生出很有意思的结论也能帮你把这块数据结构彻底打牢。
