说实话写到第五十七天还能保持对图论的清晰感已经说明前面的基础打得很扎实了。这一天的内容在训练营里重量级很高最小生成树MST是面试中“图论三件套”之一和最短路径并列但考察方式更偏实现细节和算法选型。Prim和Kruskal这两个名字你肯定听过但真正能讲清楚“为什么这么做”、“什么时候用谁”、“代码坑在哪”的人其实没那么多。这篇文章我打算把两个算法拆开揉碎讲一遍。不光是贴代码还会把背后的贪心逻辑、数据结构选型、复杂度差异、以及刷题时最常踩的坑全部说清楚。不管你是刚学到第五十七天还是回头复习准备面试这篇都值得慢慢看完。1. 先搞清楚最小生成树是什么以及我们为什么卡在这里1.1 这类题到底在说什么先花点时间把问题本身定义清楚。最小生成树针对的是无向连通带权图。所谓生成树就是从图中挑出n-1条边把这n个节点连成一个连通且无环的结构。连通和无环这两个条件缺一不可因为无环的连通图天然就是树形结构。而“最小”两个字指的是这些边的权重总和尽可能小。听起来很简单对吧但笨办法根本行不通。如果图有n个点、m条边所有可能的生成树数量是惊人的指数级枚举连小规模都扛不住。所以需要贪心策略而Prim和Kruskal就是两个从不同角度实现贪心的经典方案。举个例子帮大家建立直觉。假设你是一个小城镇的规划者要在几个村庄之间修路目标是让任意两个村庄都能通过新修的路互相到达同时修路的总成本最低。这就是一个标准的MST问题。村庄是节点可能的道路是边道路成本是权重你要选一组边把大家连起来花费最少。训练营里常见的题目也会直接这么描述给定一个带权无向图返回最小生成树中所有边的权重之和或者要求你输出树本身。LeetCode上类似的题比如某道经典的“连接所有点的最小费用”本质就是把坐标转成边权然后跑一遍MST。1.2 两种算法的大方向加点 vs 加边很多人第一次学这两个算法的时候容易懵因为明明解决同一个问题思路却完全不一样。实际上这俩算法代表了两种截然不同的贪心视角。Prim算法是“加点法”。它从任意一个节点出发维护一个“已经在生成树里的节点集合”每一步都从“集合外”找一个离集合最近的点把它拉进来同时把这条最短边收入树中。重复这个过程直到所有点都进来。这个过程像一个不断扩张的领地每一步都在往外吞并一个相邻节点。Kruskal算法是“加边法”。它完全不管点的顺序而是把图上所有边按权重从小到大排序然后一条一条看如果这条边的两个端点还没有被连在一起也就是不形成环就把它选进生成树否则丢掉。直到选满n-1条边为止。这个过程像一个修路工人把候选的道路按成本从低到高依次铺设只要不绕成一个圈就铺下去。这两种视角的差异直接决定了它们的数据结构选型、复杂度表现和适用场景。下面我分开细讲。2. Prim算法精讲挨个拉人进群的动态过程2.1 核心思路与数据结构Prim算法最直观的理解是“维护一棵不断长大的树”。它不需要关心全局的边只关心当前这棵树和外界之间的“最短切边”。算法开始前随便选一个起点比如节点0。我们把它加入树集合然后用一个数组minDist[]记录所有节点到当前树集合的最近距离。注意这里不是到某个固定起点的距离而是到“整个集合”的距离。每次迭代做两件事第一在所有未加入集合的节点中找出minDist最小的那个节点把它加进集合第二用这个新节点的所有边去“松弛”剩余节点的minDist。这里的松弛逻辑比最短路径简单不需要加和直接取min就可以。这个流程一直重复n次直到所有节点都进集合。如果中途发现某个节点除了INF以外根本选不出来说明图不连通最小生成树不存在。数据结构上朴素Prim通常配邻接矩阵因为稠密图场景下O(V²)的找最小操作比堆操作更稳定。堆优化Prim则配邻接表适合边数较少的图用优先队列维护“所有跨越树内外的边”每次取堆顶即可。2.2 朴素版Prim适合稠密图朴素Prim的代码结构非常对称写熟了基本是模板级别的肌肉记忆。下面给出核心C代码#include bits/stdc.h using namespace std; const int INF INT_MAX; int prim(int n, vectorvectorint graph) { vectorint minDist(n, INF); // 到树集合的最小距离 vectorbool inTree(n, false); // 是否已在树中 minDist[0] 0; int result 0; for (int i 0; i n; i) { // 1. 找未加入集合且距离最小的节点 int u -1; for (int j 0; j n; j) { if (!inTree[j] (u -1 || minDist[j] minDist[u])) { u j; } } // 2. 如果找不到可达节点说明图不连通 if (minDist[u] INF) return -1; // 3. 加入集合累计权重 inTree[u] true; result minDist[u]; // 4. 用新节点的边更新minDist for (int v 0; v n; v) { if (!inTree[v] graph[u][v] minDist[v]) { minDist[v] graph[u][v]; } } } return result; }注意几个细节找最小节点那一步如果写成int u -1再比较可以避免用一个很大值初始化。result累加的其实是minDist[u]不是graph[pre][u]。虽然数值一样但前者语义更清晰这个节点到已成型树的最小距离。如果图里初始给的起点无法到达任何其他节点要提前返回-1。朴素Prim的时间复杂度是O(V² E)实际情况常写作O(V²)因为外层循环找最小值是V次每次O(V)内层松弛总共遍历所有边。对于稠密图也就是边数接近V(V-1)/2的场景这个复杂度够好因为边再多也无所谓反正找最小值只需要按点扫描。2.3 堆优化版Prim适合稀疏图当图的点数到达几万、边数达到几十万时朴素Prim的O(V²)就不行了。这时候需要用邻接表 优先队列实现堆优化版本。核心思想是不每次扫描所有点找最小值而是把“树集合扩张后产生的新边”全部扔进最小堆。堆顶天然就是当前所有跨越树内外的边中最短的那条。如果堆顶边的两个端点都已经在树内说明这条边已经没用了跳过即可。#include bits/stdc.h using namespace std; int primHeap(int n, vectorvectorpairint, int adj) { const int INF INT_MAX; vectorint minDist(n, INF); vectorbool inTree(n, false); // 小顶堆pair距离, 节点 priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; minDist[0] 0; pq.push({0, 0}); int result 0, cnt 0; while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (inTree[u]) continue; // 已加入跳过 inTree[u] true; result d; cnt; for (auto [v, w] : adj[u]) { if (!inTree[v] w minDist[v]) { minDist[v] w; pq.push({w, v}); } } } if (cnt ! n) return -1; // 不连通 return result; }这里坑点主要有两个一是重复入堆。同一个节点可能因为不同边的松弛被多次加入堆中。处理办法是用inTree标记出堆时如果已经入树就跳过。这是标准写法见一次就会了。二是为什么用minDist。理论上可以只拿边判断但用minDist数组保存每个节点到树的最小距离可以避免堆里残留的旧边反复被当作候选。否则你可能会在堆里存大量无效边影响效率。堆优化Prim的复杂度是O(E log V)建堆过程O(E)每次pop和push都是log级别。当边数远少于V²时它明显优于朴素版。2.4 Prim正确性的直观解释为什么每次选离树集合最近的点就一定能得到全局最优这背后是切分定理Cut Property。把当前树内节点看成一组树外节点看成另一组。任何跨越这两组的边必然有一条会出现在最终的最小生成树中。Prim每次挑的就是跨组边里最短的那条根据切分定理这条边一定属于某个最小生成树。因为如果存在一个最优解不包含这条边把这条边加进去会形成一个环环里一定还有另一条跨组边它的权重大于等于这条最短边去掉那条再换过来总权重不会增加。所以每一步贪心都不会把路走死局部最优累积起来就是全局最优。这个解释大家面试时一定要能说出口比“我觉得它是对的”有说服力得多。3. Kruskal算法精讲排序后一条条挑边3.1 核心思路与并查集Kruskal算法的视角完全不同。它不看点只看边。先把所有边按权重从小到大排序然后从头到尾扫描能选就选不能选成环就跳过。问题来了怎么快速判断“选了这条边会不会成环”答案是并查集Union-Find。并查集维护的是节点之间的连通关系。初始时每个节点自己是一个集合。每选中一条边(u, v)就检查u和v是否在同一个集合里。如果在说明已经有一条路径连通它们了再加这条边必定成环如果不在说明这条边连接了两个不同的连通分量选它不会成环于是合并这两个集合。这个判断过程经过路径压缩和按秩合并优化后单次操作几乎是常数级别的所以整个算法的瓶颈完全在排序上。3.2 完整实现流程Kruskal完整实现比较简单先定义边的结构体然后排序再套并查集。#include bits/stdc.h using namespace std; struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; vectorint parent; int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); // 路径压缩 return parent[x]; } bool unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return false; parent[ra] rb; // 不按秩合并问题也不大路径压缩兜底 return true; } int kruskal(int n, vectorEdge edges) { sort(edges.begin(), edges.end()); parent.resize(n); iota(parent.begin(), parent.end(), 0); int result 0, cnt 0; for (auto e : edges) { if (unite(e.u, e.v)) { result e.w; cnt; if (cnt n - 1) break; // 提前结束 } } if (cnt ! n - 1) return -1; // 非连通 return result; }这里的优化点有几个边结构体重载运算符让sort直接按边权排序简洁。提前break当已经选了n-1条边时生成树已经成型不需要再扫描剩余边。iota(parent.begin(), parent.end(), 0)一行初始化并查集比手写for循环清爽。判断非连通正常连通图选满n-1条边肯定结束如果没选满说明有的点永远连不上。Kruskal的时间复杂度是O(E log E)排序是最大头。并查集部分几乎可以忽略。空间上只存边的数组和并查集非常省。3.3 Kruskal正确性的直观解释Kruskal的正确性也可以从切分定理解释但有个更应试的说法。排序后我们从小到大考虑每条边。当扫描到边e时如果它的两个端点不在同一个连通分量里说明它连接了两个不同的区域。此时图中所有权重小于e的边都已经处理完了并且我们已经尽量选了能选的。如果存在某个最小生成树不包含e那么把那棵树加上e必定形成环环里至少有一条边连接着这两个分量且它的权重大于等于e。把它换成e总权重不会变大。所以选e永远不会错。这个“不需要的边永远不会变得有用”的直觉也很重要一条被跳过的边因为它的端点已经连通后面无论如何都不会再成为连接不同分量的桥。所以它的机会窗口只有这一次。4. 两个算法放一起比到底选哪个4.1 复杂度对比与题目线索很多人的困惑不是写不出来而是拿到一道题不知道用哪个。我整理了一个对比表做题时照着匹配就行。算法思想时间复杂度空间复杂度适合场景朴素Prim加点法O(V²)O(V²)稠密图V较小比如 V ≤ 2000堆优化Prim加点法 堆O(E log V)O(V E)边数不太大的图Kruskal加边法 并查集O(E log E)O(E)稀疏图或者边列表天然容易获取实战里的判断标准很简单题目给了邻接矩阵或者点数是几百、几千级别村庄之间任意两点都有路也就是稠密图优先写朴素Prim。代码短还不容易因为堆的pair顺序写错。题目明确告诉你边数远小于V²例如V很大但E只有2V左右优先Kruskal。因为你只需要把边排个序连邻接表都不用建。如果题目要求输出生成树本身而不是只输出权重Kruskal更直观因为选中的边就是一组(u, v)Prim也能做得额外记录每个节点是从哪条边进来的。严格说堆优化Prim和Kruskal在稀疏图上复杂度同一量级但Kruskal实现更不容易出bug所以我在面试里更推荐它除非考官明确考察Prim。4.2 同一个题用两种解法过一遍为了验证两个算法确实殊途同归我拿一个手写的样例跑一遍。假设图有5个点边如下(0, 1) 2 (0, 3) 6 (1, 2) 3 (1, 3) 8 (1, 4) 5 (2, 4) 7 (3, 4) 9用Prim从0开始先选(0,1)边2此时树集合{0,1}到2最近的是边3选2树集合{0,1,2}到3最近的是边6选3到4最近的是边5选4。总权重236516。用Kruskal排序边序为2、3、5、6、7、8、9。选(0,1)2选(1,2)3选(1,4)5选(0,3)6此时已有4条边结束。总权重还是16。结果一致过程不同这个例子很适合给面试官展示你对两种思路都理解。5. 刷题和面试里的常见坑5.1 一堆人都会踩的细节负权边没问题。这是MST和最短路径最不一样的地方。Dijkstra遇到负权边会崩但Prim和Kruskal根本不在乎因为它们的贪心依据是“边权相对大小”的全局比较不需要像Dijkstra那样依赖路径累加。所以看到负权别慌照常跑。自环要跳过。Kruskal扫描到(u, u)的边时find(u) find(u)必然跳过不会影响结果。Prim的邻接矩阵也能处理自己到自己的距离为0不会比别的边更小。重边取最小。用邻接矩阵存图时多条同点对边要取最小值。用邻接表存图则无所谓两个算法都能正确处理只是堆里可能多几条残余边不影响结果。非连通图必须判。很多萌新忘了判断最终选中的边数是否达到n-1。如果你只是输出权重没检查连通性结果会是“伪答案”还容易输出一个很小的数让人误以为对了。面试时一定要问清楚“图保证连通吗”否则代码里记得补判断。Prim起点任意。有人担心从不同点开始会得到不同结果实际不会因为MST不唯一但总权唯一。你从任何一个点开始跑朴素Prim总权重都一样。5.2 面试常追问的几个点我把自己面试时被问过、以及陪跑时听别人被问过的问题整理一下。“Prim和Dijkstra有什么区别” 这个问题几乎必问。Dijkstra维护的是“到源点的最短距离”更新时要dist[v] dist[u] wPrim维护的是“到树集合的最短距离”更新时是minDist[v] min(minDist[v], w)。后者不需要累加逻辑更简单。“Kruskal的并查集如果不做路径压缩会怎样” 复杂度退化到接近O(E log V)甚至更差但正确性没问题。面试时先说路径压缩的原理再补一句“按秩合并也能进一步优化”。“如果让你处理百万级点的图选哪个” 先确认稠密还是稀疏。如果是完全图但点很多V²空间根本存不下只能用Kruskal把边弄出来排序但边数量也爆炸实际场景中这种数据规模通常有特殊限制。如果是稀疏图Kruskal是首选。“能不能用Kruskal求最大生成树” 可以把排序从小到大改成从大到小就行。这个衍生知识点偶尔出现在笔试里一句话即可拿下。5.3 我的学习顺序建议训练营走到第五十七天前面应该有并查集和堆的基础。我的建议是先裸写一遍朴素Prim把循环逻辑吃透。再写一遍堆优化Prim体会为什么需要minDist和inTree。最后写Kruskal你会发现代码量大幅减少核心就是并查集。三个版本都过一遍之后MST这块就算真正焊死了。如果时间紧至少把朴素Prim和Kruskal写熟堆优化版作为进阶理解。6. 最后再说一点自己的体会我一开始学这两个算法的时候总觉得Kruskal更“好懂”因为排序后一条条挑边特别符合直觉。后来刷题多了才发现Prim的“扩展”思想在很多变种题里才是真正的主力。比如让你求“连接所有点的最小成本的变体”、“最小生成树中瓶颈边”相关的问题往往需要你回到Prim的切分视角去思考。所以两个算法真的不能偏废。还有一个小技巧想分享给大家面试手写代码时Kruskal的并查集如果让你现场写偶尔会脑子空白。我的习惯是先写find再加unite然后写主体。而Prim我更喜欢先写邻接矩阵版本因为它不需要优先队列的pair比较出错概率低。你可以在平时练习时给自己定好“默认顺手版本”面试时直接调用肌肉记忆能省下很多压力。第五十七天是个容易让人疲惫的阶段但图论这部分学完之后你会发现很多所谓难题其实就是基础算法的排列组合。把Prim和Kruskal真的吃透后续遇到更复杂的最小生成树变种你也只是在上层加细节而已内功早就够了。