聊最小生成树MST的时候很多人的第一反应就是Kruskal算法和Prim算法这两个名字再往下追问一句“为什么这两套流程能保证得到最优解”就很容易卡住。我当初学的时候也是先背模板背到后来处理各种变种题才意识到十个MST相关做法里九个半都在反复使用同一条性质在某个切分里选最小的横跨边一定不会把结果做差。先把这句话刻在脑子里后面所有代码都会好懂很多。这篇文章我想把MST性质、Kruskal和Prim算法穿成一条线来讲不只给能跑的代码更想把“每一步为什么要这么做”说透。适合三类人看准备算法面试但总在模板边缘反复横跳的开发者、需要快速上手图算法做工程方案的工程师、以及单纯想把MST彻底弄明白的学生。如果你只是想要一段能交作业的代码直接往后翻也能找到但我还是建议你把性质部分看完因为后续的次小生成树、最大生成树、最小瓶颈生成树全部是从这几个性质长出来的。1. 最小生成树到底在解决什么问题1.1 从最省成本的布线问题说起先抛开术语看一个我最近在模拟项目X里遇到的实际问题有若干个机房节点需要互相连通每两个节点之间可以铺设线路但不同节点对的成本不一样。目标不是让某个节点到另一个节点走最短路径而是要让整个网络连通的前提下总铺设成本最低。这种“全局连通成本最低”的问题就是最小生成树的经典场景。很多人会把它和最短路搞混。最短路关心的是单点出发到单点结束的最小代价比如“从A到B走哪条路最近”而MST关心的是把一整张网拉起来的整体代价比如“这条线缆网怎么铺最便宜”。最短路的结果是一条路径MST的结果是一棵树树的边数永远是节点数减一这是它最明显的特征。如果你平时刷题这类题的描述往往是给定n个点和m条带权边求最小生成树的总权值或者输出其中一条边。如果你在做工程MST的用武之地也远不止机房布线聚类分析、图像分割、电路设计、低延迟组网都能看到它的身影。后面第4节我会专门展开讲应用现在先把定义坐实。1.2 生成树、MST与最小生成森林的定义边界一张无向连通图G(V,E)如果有|V|-1条边能连通所有顶点且不形成环这棵子图就是一棵生成树。注意两个关键词连通、无环。只要满足这两个条件边数一定是|V|-1这是树的基本性质。如果边数少于|V|-1一定有不连通点如果边数多于|V|-1一定有环。所以生成树本质就是从图中选出最“经济”的一组边把点全部串起来。MST就是所有生成树里权重总和最小的那一棵。这里有个容易忽略的点MST不一定唯一但权重总和一定唯一。比如三个点三条边权重分别是1、1、2那选择两条权重为1的边可能是两种情况权重总都是2。处理这种相等权重的边时两个经典算法怎么选都无所谓因为最终答案权重不会变树木身会长得不一样而已。还有一个边界情况如果图本身不连通那整张图不存在生成树。这时两个算法算出的其实是最小生成森林也就是每个连通分量各得一棵MST。实战中判断方式很简单统计最后选出的边数是否为n-1如果不是说明图不连通。有些人把这个细节叫“边界处理”但我更愿意说它是解题前必须想清楚的第一步。1.3 MST性质到底在说什么切分、回路与安全边理解MST的钥匙是下面这三条性质。第一条叫切分性质Cut Property。把图的顶点任意分成两个非空集合S和V-S所有横跨这两个集合的边权重最小的那条一定属于某棵MST。这里的“某棵”很关键因为可能有多个MST但至少有一棵会包含它。原因是反证法假设一棵MST不包含这条最小横跨边e那把这棵树加上e必然形成一个环环上一定还有另一条横跨S和V-S的边f且f的权重大于或等于e。把f换成e树的连通性不变总权重不增加所以新树也是一棵MST而且包含e。说白了你从中间切一刀两堆点之间总得有一条边连着选最便宜的那条连接线永远不亏。第二条叫回路性质Cycle Property。任意一个回路里权重最大的那条边不属于任何一棵MST。证明同样朴素如果某棵MST包含了回路上的最大边e删掉e后树会分成两个连通块而回路里必然存在另一条边能重新把这两个块连起来这条边的权重严格小于e最大边只有一条时替换之后得到更小的生成树矛盾。如果回路里最大边有多条任意删掉一条也不会破坏最优性因为替换后权重不变。这条性质正是Kruskal跳过成环边的理论依据。第三条其实是前两条的合并每个切割里都能找到一条“安全边”贪心地把它选进当前森林不会堵死通往最优解的路反过来回路里最大的边是“危险边”永远可以不选。最小生成树类算法无论怎么变形本质上都是在“选安全边”和“扔危险边”之间反复操作。理解了这三条Kruskal和Prim就不再是两个孤立模板而是同一套图论性质的两个投影。1.4 为什么说MST性质是Kruskal和Prim的共同地基Kruskal和Prim看起来差别很大一个全局排序慢慢试边一个从单点往外长树。但它们的每一步决策都能落到上面某条性质上。Kruskal把所有边按权重从小到大扫遇到“不成环”的边就收下。它选边时当前图已经被之前选中的边拆成了若干连通分量这条边连接的两个分量其实就构成一个切分因为是全局升序扫描这条边正是横跨这两个分量之间“最先出现”的边也就是最小边。因此选它是切分性质在保底。反过来它跳过成环的边本质是回路性质在发挥作用此刻这条边在某个环里已经算大边了不选它不会错。Prim维护一个“已选点集合S”每次都挑横跨S和V-S的最小边。这个动作几乎就是切分性质的原样复刻S就是切分的一边剩下的点是另一边选最小横跨边安全。所以它不需要像Kruskal那样关注全局最大边只要盯着集合边界就可以了。后面的很多变种题比如求次小生成树、判断某条边是否可能在MST中都是把这两条性质反过来再正过去用。我见过太多人把Kruskal的并查集倒背如流却不会做次小生成树原因不是代码不熟而是性质没进脑子。所以这一节的标题虽然“抽象”但它是最值得反复看的地方。2. Kruskal算法从“从小到大试边”开始2.1 一句话记住Kruskal从小到大试边不成环就收Kruskal的理解成本很低一句话就能说完把边按权重从小到大排序依次尝试每条边如果这条边连接的两个点还没有连通就把它加入生成树否则跳过。直到选满n-1条边为止。听起来像一个很自然的贪心但“自然”不代表“显然正确”。随便乱贪心很容易翻车比如背包问题这种按单位价值从大到小选并不能保证全局最优。但Kruskal不一样它的每一步都被第1节的切分性质和回路性质保护着。排序保证了“当前遇到的不成环边一定是在某个切分里最便宜的横跨边”跳过成环边保证了“我们永远不碰回路里没必要的大边”。两个性质互相配合最终拼出一棵MST。一个常见问题是排序后遇到相等权的边该选哪个答案是都行。因为相等权的边互换不会改变总权重最多改变树的形状。你唯一要保证的是“不重不漏”地处理每条边而不是人为加额外规则。另一个小技巧是当已经选满n-1条边时可以提前break不用把边表扫完这在边特别多的时候能省不少时间。2.2 并查集实现与代码示例Kruskal的核心数据结构是并查集Union-Find。它需要快速回答两个问题这条边的两个端点当前是否连通如果把它们合并能不能快速做“连通”在这里不是指图中天然有边而是指在当前已经选中的生成树边里两个点是否已经被串到了同一个连通分量。所以需要在每次选边后把两个端点所在的集合合并。并查集的实现有很多细节我习惯用一个带路径压缩和按集合大小合并的版本。路径压缩降低找根的成本按集合大小合并防止树退化成链。写出来的模板大概是下面这个样子我先给完整代码再解释关键行。class DSU: def __init__(self, n): self.parent list(range(n)) self.size [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): ra self.find(a) rb 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(n, edges): # edges 是 (权重, u, v) 的列表 edges.sort(keylambda e: e[0]) dsu DSU(n) mst [] total 0 for w, u, v 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值得注意的地方有三个。第一find里用while实现路径压缩不要写递归版本否则在Python里大数据量时容易递归深度过大。第二union返回False表示两端本就在同一个连通分量这条边如果硬选会成环直接跳过这正是回路性质在代码里的体现。第三最后判断len(mst) ! n - 1这是我在真实项目里吃过亏的地方忘掉这个判断会让人误把一片森林当成MST输出。2.3 贪心正确的反证逻辑Kruskal的正确性证明是算法课上的常客但很多人听完就忘。我试着用更容易记的说法再讲一遍。假设Kruskal的算法执行到某一步它准备把边e(u,v)加入当前森林。这时u和v分别位于两个不同的连通分量C1和C2。因为算法按权重从小到大扫描而且之前比e轻的边都已经处理过了所以所有能连接C1和C2的边里e一定是最先被扫到的它的权重是这些横跨边中的最小值。按切分性质一定存在一棵MST包含这条最小的横跨边。因此Kruskal选择它没有牺牲最优解。更严谨的归纳式证明会这样做用数学归纳法证明算法的第k步选出的k条边一定可以扩展成某棵MST。第k步选e时e连接两个分量切分性质保证存在一棵包含e且包含之前k-1条边的MST。一步接一步最后kn-1时算法得到的树就是MST。这套“安全边”逻辑是图论贪心算法的通用模板Kruskal只是把它用在了边集上。理解了反证逻辑之后你就能回答一个很常见的面试追问为什么排序后跳过成环边不会漏答案因为被跳过的边在某个回路里已经算“大边”了而每棵MST都不需要回路里的大边跳过它正是回路性质在替你排除错误选项。2.4 实操心得相等权边、不连通图与性能陷阱我在实际写Kruskal时最常踩的坑有三个。第一个坑是顶点编号从0还是从1开始。很多题面说“1到n个点”代码里直接range(n)初始化并查集然后把输入的u减1否则会数组越界或漏判。我习惯统一用0-based在输入解析时就处理掉省得后面一错再错。第二个坑是无向图的边表重复。有人从邻接矩阵转边表时会一条无向边存两遍排序后处理也还好因为第一次已选第二次必然成环跳过但时间和内存白白浪费一倍。如果边数上百万这会直接影响程序能不能跑完。正确的做法是边表只存每个点对一次或者存两条但在遍历时只取一条。第三个坑是图不连通时最后边数不等于n-1。我建议在输出前加一行断言或者像上面的代码一样返回None宁可在调试阶段发现也不要带到线上环境。另外如果内存很紧边表不需要额外保存索引直接用(w, u, v)元组排序就行Python里元组排序默认按第一项排权重相同时再比较端点这个顺序不影响结果。性能上Kruskal的瓶颈几乎都在排序O(E log E)。并查集操作的均摊复杂度是反阿克曼函数可以近似看成常数。所以在稀疏图里Kruskal优势明显因为E接近V排序边的数量不大。但如果是稠密完全图E接近V^2排序上百万甚至千万条边就很吃劲这时候Prim的O(V^2)朴素做法反而更合适。3. Prim算法从一个点开始“长”出一棵树3.1 核心思想维护已选集合与未选集合的切口Prim的思路和Kruskal完全不同它不全局排序而是从任意一个点出发不断把“新的点”拉进已选集合S。每次拉入哪个点就是横跨S与V-S的所有边里权重最小的那条边所连接的那个点。这个动作重复n-1次就得到一棵MST。为什么从任意点出发都行因为初始时S只有一个点切分性质只要求把一个集合切成两边并不要求这两边大小如何所以即使S只有一个顶点它的所有邻边里最小那条依然属于某棵MST。这个“任意起点”是Prim算法最容易被忽略的巧妙之处很多初学的人会担心起点选错其实完全不用担心最终总权重一定一样。实现上需要维护一个数组dist[v]表示点v到当前S集合的最短距离更精确地说是“v与S中某个点直接相连的边的最小权重”。每次从未加入S的点中找出dist最小的那个加入S然后用它去更新其他未加入点的dist。这个过程特别像Dijkstra跑最短路但两个算法的dist定义有本质区别下面我会展开讲。3.2 朴素实现O(V^2)的写法朴素Prim适合用邻接矩阵存储的稠密图。它的循环里每一轮都要在未访问点里扫一遍找最小值然后用这个点去更新所有邻接点。总复杂度是O(V^2)不依赖边的数量所以在完全图这种极端稠密场景下它反而能吊打需要排序的Kruskal。看一个完整的Python实现def prim_naive(n, matrix): INF float(inf) visited [False] * n dist [INF] * n dist[0] 0 total 0 for _ in range(n): # 找出未访问且距离最小的点 u -1 best INF for i in range(n): if not visited[i] and dist[i] best: best dist[i] u i if u -1: return None # 图不连通 visited[u] True total dist[u] # 用 u 去更新其他点离集合S的距离 for v in range(n): if not visited[v] and matrix[u][v] dist[v]: dist[v] matrix[u][v] return total这里dist[u]表示点u到已选集合的最小直接边权重不是从某个源点到u的路径总长。更新时用的是matrix[u][v] dist[v]写成取最小值而不是dist[u] matrix[u][v]。我见过太多人把这里写成Dijkstra的松弛公式结果算出来的东西完全不是MST。记住Prim的dist是“点到集合”的距离Dijkstra的dist是“点到源点”的距离一个比较直接边权一个累加路径权这是两类算法最容易混淆的一点。3.3 堆优化实现O(E log V)的写法如果图是稀疏的用邻接表加最小堆优化Prim会更实用。堆里存二元组(边权, 点编号)每次弹出最小边权的点如果这个点已经被访问过就跳过否则选它并把所有邻居中未访问点的边权压入堆。这里的“跳过”就是所谓的懒惰删除。因为同一个点可能通过不同边被多次压入堆但堆顶弹出的那个一定是当前所有备选边里最小的所以第一次弹出某个点时它对应的边就是横跨集合的最小边。后面再弹出同一编号的点直接忽略即可。import heapq def prim_heap(n, adj): visited [False] * n pq [(0, 0)] # (边权, 点) total 0 selected 0 while pq and selected n: w, u heapq.heappop(pq) if visited[u]: continue visited[u] True total w selected 1 for v, w2 in adj[u]: if not visited[v]: heapq.heappush(pq, (w2, v)) if selected n: return None # 图不连通 return total这段代码有一个细节total w加了第一次弹出的0权重边权起点自己先入堆所以没啥问题。理论上每次弹出一个新点w就是连接它到S集合的那条边权重。如果想要记录生成树的边可以在push时额外带上父节点信息但不影响总权重计算。堆优化的时间复杂度和堆操作次数相关每个边最多被压入一次所以是O(E log V)。但如果图的边特别多堆的常数和内存开销也会变大这也是为什么稠密图不一定选堆优化的原因。3.4 三个初学必踩的坑与正确性解释第一个坑是visited标记的时机。正确做法是弹出堆顶时标记visited而不是在压入堆时就标记。如果你在push时标记该点已访问那后面如果有一条更小的边指向同一个点就会被错误跳过导致结果偏大。我第一次写Prim堆优化时就是这么错的小图正确大图错调到怀疑人生才意识到是标记时机的问题。第二个坑是dist语义混同。Prim里的dist只记录“到集合的最小边权”更新时永远取min不是累加。即使图上存在负权边Prim依然可以正常工作因为它不像最短路那样需要在路径上不断累积只关注“当下哪个点到集合最近”。这一点和Dijkstra有本质区别Dijkstra在有负权边时会出错Prim则完全不受影响。第三个坑是邻接表漏加反向边。无向图用邻接表时必须对每条无向边存储两次比如u到v存一次v到u再存一次。只存一次会让Prim从一个方向访问不到另一个方向的邻居轻则漏边重则直接把图切开最后返回不连通。这个问题在Kruskal的边表里不明显因为边表天然无向所以两个算法的数据组织方式一定要分清楚。4. Kruskal和Prim怎么选对比、场景与扩展应用4.1 一张表看懂复杂度与适用图很多文章会把两个算法各讲一遍就结束但实际刷题和做工程时“选哪个”往往比“会不会”更重要。下面这张表是我自己整理出来的一张速查卡。对比维度Kruskal算法Prim朴素实现Prim堆优化驱动方式边驱动全局排序点驱动集合生长点驱动集合生长核心数据结构并查集邻接矩阵数组邻接表最小堆时间复杂度O(E log E)O(V^2)O(E log V)空间复杂度O(E)O(V^2)O(VE)适合场景稀疏图、边数少稠密完全图中等密度、大图稀疏主要缺点边多时排序代价高矩阵占用大V不能太大堆常数大代码稍复杂能否处理负权边可以可以可以图不连通时返回森林或报错返回None返回None有一个很反直觉的点堆优化Prim的时间复杂度看起来比朴素Prim好很多但在完全图里它不一定更快。完全图的E约等于V^2堆操作要对O(E)条边做log级别维护而朴素Prim每轮扫V个点总共O(V^2)省去了堆的log因子和指针跳转开销。实测下来V在几千到一万的稠密图朴素Prim往往更稳。Kruskal的优势场景则是边数明显少于V^2的稀疏图。比如一个10万个点、20万条边的普通道路网络Kruskal排序20万条边的开销很小而如果非要用O(V^2)的朴素Prim光是那个双重循环就要跑到百亿级别直接不可用。所以选型前先估算V和E的量级再决定算法。4.2 真实场景下的选型经验我在模拟项目X里同时遇到过两种极端图。第一次是站点少但几乎所有节点都能直连我直接用邻接矩阵存一个规模接近完全图的网络跑朴素Prim循环几万次就出结果代码短且不容易出错。第二次是图很大但边很少几百个节点只允许保留有限几条潜在通路这时候Kruskal明显更舒服边表排序后很快还能顺便用并查集判断整个网络连不连通。如果你的工程场景里边权不是预先存好的而是每对点之间有一个计算函数动态生成那么邻接矩阵朴素Prim更方便因为它不需要先枚举所有边再排序直接在矩阵里读权值即可。反过来如果边集来自外部数据流一次读一大块Kruskal需要先把所有边收集起来排序但如果是允许增量的场景Prim可以在读取过程中慢慢生长树内存压力会更小而灵活。还有一类特殊情况某些边已经被强制要求保留。比如我要在MST里强行包含某条非可选边又不想破坏整体最小性。Kruskal的处理方式很直接先把这条边加入并查集然后再跑正常流程。Prim处理这种情况稍麻烦一般做法是先人工把这条边两端点标记为“已连通”再在剩余图中继续。这种“必须先包含/必须先排除一些边”的变形工程里比想象中常见理解算法的数据结构后会发现都不难改。4.3 MST不只是最小生成树从性质延展出的变种MST相关题目往往不是直接求最小生成树而是围绕MST性质改成各种变体。这里简单列几个高频方向。最大生成树把Kruskal的边表按权重降序排序或把边的权重取负再跑最小生成树就得到最大生成树。切分性质和回路性质在符号翻转后依然成立所以正确性不变。次小生成树想求严格次小的生成树常用思路是先用Kruskal求一棵MST然后枚举所有不在树里的边试图把它加入树中必然会形成环再删掉环上除该边外的最大边计算新权重取全局最小。这里的“删环上最大边”又用到了回路性质所以如果没吃透MST性质次小生成树的代码会让人看得云里雾里。最小瓶颈生成树要求生成树中最大边权尽可能小。结论是一条生成树是MST当且仅当它是最小瓶颈生成树。所以解法就是直接求MST这是MST性质的经典推论面试里经常拿来当概念题。这些变种的意义不只是刷题在分布式系统组网、雷达通信链路选择、图像区域分割里都有对应场景。理解一条性质能带活一片问题这就是为什么我在开头反复强调别只背Kruskal和Prim的名字。5. 常见问题与排查技巧实录5.1 验证结果对不对的三板斧很多人在本地跑样例能过一提交就错最尴尬的是不知道错在哪。我总结了一套验证MST代码结果的三板斧按顺序检查基本能定位大部分问题。第一板斧点边数是否匹配。如果图有n个点选中的边数必须是n-1。少于n-1说明图不连通或者算法里某个continue漏加了边多于n-1说明你的生成代码里有环多半是并查集合并条件写反了。第二板斧把总权重和暴力枚举的小图答案比对。n不超过8时可以用递归枚举所有边的选与不选检查连通且无环后统计最小权重和算法结果对比。这种暴力对拍能覆盖绝大多数逻辑错误。第三板斧检查无向边是否被重复计数。如果输入边表是无向边但被存成两条Kruskal第二次遇到时并查集会跳过不影响结果但Prim如果邻接表里重复存同一条边会在堆里产生更多重复项也不影响最终权重却在内存和时间上白白浪费。如果结果偏大优先查visited标记时机而不是怀疑性质错了。5.2 并查集与堆优化常见翻车现场并查集翻车通常是递归find导致栈溢出或者路径压缩写成了“只在某个方向上压缩一半”。我建议直接用迭代式find这样最安全。另一个隐蔽问题是初始化size数组时没有全部置1有些人不小心用[1]乘了n次或者从某个未知值开始累加合并时的“小挂大”策略就失效最坏会退化成链。可以用一个随机生成的小图多跑几次来验证并查集的合并次数是否正好等于n-1。堆优化Prim最常见的翻车点是重复项太多导致内存爆炸。每个点会被多个邻居push多次在大图上如果相邻边权都很小堆里可能堆出上百万条记录。解决办法是懒删除加“dist优化剪枝”在压入堆前如果当前边权已经不小于dist[v]就完全不压弹出时再检查v是否已访问。这样可以大幅减少堆中无效项。还有人会忘记在弹出前判断visited直接开始更新邻居导致同一个点被重复选中、重复累加权重答案必然出错。最隐蔽的一个问题是Prim的堆优化里用大根堆而不是小根堆。Python的heapq默认是小根堆但有些语言需要自定义比较器。如果写成了大根堆算法会把最大横跨边每次都选进树里跑出来的结果看着也像一棵树但权重完全错。遇到这类问题我建议在代码里加一段断言assert total expected或者对拍小图。5.3 大图下的优化方法当V和E都到几十万甚至上百万时语言层面的细节开始决定成败。Python里我一般会做几件事边表直接存成元组列表排序时用keylambda e: e[0]只按权重排不要默认排序去比较端点并查集find用局部变量缓存parent减少属性访问开销把sys.stdin.buffer.read()整块读取再split避免逐行调用输入函数。Prim堆优化在大图上的另一个优化点是使用两个数组dist和in_tree每次从堆里弹出节点时再懒更新dist或者直接使用“索引堆”避免堆内重复项。不过工程上大多数场景用懒删除已经够了索引堆代码复杂度高收益只在极端图上明显。我建议先跑一版简单实现用实际数据量测一下内存和耗时再决定要不要折腾更复杂的数据结构。如果图本身就是完全图且边长由坐标欧氏距离给出可以完全不存边表在朴素Prim里动态计算距离内存直接降到O(V)。这也是工程和算法题的一个巨大差异题目通常只会把所有边给你但真实项目里很多边是规则生成的存不存得下、存不存得起要提前想清楚。5.4 用随机小图暴力对拍最后分享一个我自己一直在用的调试习惯每次写完MST模板先不急着交生成一批随机小图跑对拍。具体做法是随机生成n个点随机生成m条边保证图连通然后用暴力算法枚举所有生成树取最小值和Kruskal或Prim输出对比。n控制在8以内因为8个点的生成树数量最多也只有2的8次方量级的子集组合暴力计算很快。对拍脚本一旦跑起来几百组随机数据全绿说明算法的正确性基本有保障。后面再遇到WA问题通常出在输入输出边界、节点编号、图不连通等“非算法”部分而不是核心逻辑。这个方法看似笨但比盯着代码一行行抠快得多也是我写图算法时最推荐大家掌握的自测手段。6. 写在最后理解性质比背模板更重要我在实际开发里调试MST相关代码的体会是代码本身不是难点难的是改一个输入条件后你还能不能立刻判断该用哪个算法、该在哪一步做调整。比如题目里突然加了“必须包含某条边”“允许存在相同权重”“图不连通时输出森林”这些本质上都是在MST性质上做文章。如果你只是背了一个Kruskal模板遇到这些条件很容易手足无措如果你脑子里有切分性质和回路性质很多变形题甚至不用搜题解自己就能推出来。还有一个我在竞赛里经常用的小技巧遇到MST变种题先在草稿纸上画一个四五个点的图把切分性质和回路性质分别代进去看一轮。往往绕几圈就能找到正确做法。这个方法比在编辑器里盲改代码高效得多。希望这篇总结对你有帮助不管你是刚开始学图算法还是已经能秒写模板但想补一补原理都可以从性质这个角度再回看一遍Kruskal和Prim会有一种“原来如此”的感觉。