到了训练营第六十二天卡码网KamaCoder53这道“寻宝”题我前后提交了四次才算彻底跑通。不是题本身有多难而是我一开始把它当成最短路去想了绕了好大一圈才意识到题目里说的“打通所有藏宝点之间的道路让任意两点都能相互到达并且总花费最小”这正是教科书级的最小生成树问题。如果你也正卡在这道题上或者刚做完想回头捋一捋Kruskal和Prim的差异那这篇文章应该能给你一些实在的参考。先说结论KamaCoder53“寻宝”本质上是一道无向带权图的最小生成树题。图里有N个节点M条边每条边有一个花费你需要选择其中一部分边让所有节点连通且选出的边的总花费最小。约束条件没有特别刁钻的地方数据范围也适合用常规的Kruskal或堆优化Prim去做。真正值得琢磨的是为什么这个问题不能用最短路思路为什么最终答案一定是一棵树以及两种主流解法各自适合什么场景。这些内容我会在后面逐段展开顺手把可直接提交的C代码和调试样例也贴出来。1. 题面拆解为什么“寻宝”是所有点连通的最小花费问题1.1 从一个朴素的连通需求说起这道题的场景包装很有意思你有一张藏宝图图上散布着若干个宝藏点点与点之间有一些已经存在的道路每条道路的修建或通行成本不同。你的目标是让任意一个宝藏点都能通过若干条道路到达其他所有宝藏点求满足条件的最小总成本。这个描述里藏着两个容易忽略的关键词。第一个是“任意两点都能到达”这意味着我们的目标不是从A点到B点的某一条路径最短而是整个图作为一个整体必须连通。第二个是“总成本最小”也就是说我们要在保证连通的前提下把选中的边权之和压到最低。这两个条件组合在一起定义了一个和“最短路”完全不同的优化目标。打个比方最短路问题像你在城市里叫网约车只想从家到公司距离最短一路上经过哪些路口根本不重要而最小生成树问题像电信运营商在几个城市之间拉骨干光缆目标是让所有城市都接入这张网络至于某两个城市之间的绕行距离是多少反而不是首要考虑。这两类问题表面上都涉及“选边”和“权值”但优化的对象完全不同。1.2 生成树为什么最优方案一定没有环明确了目标是“全连通”之后一个自然的追问是最终选出的边会是什么形态假设图里有N个节点如果选择的结果包含了一个环那么去掉环上的任意一条边原来连通的节点依然连通而总成本却变小了。既然我们要的是最小成本那么任何带环的方案都必然不是最优解。所以最优方案一定是一个无环连通图也就是一棵生成树。连通N个节点至少需要N-1条边而一棵树恰好有N-1条边。所以这道题的答案必然是从M条边中选出N-1条边构成一棵生成树并且让这棵生成树的总权值最小。这就是“最小生成树”这个名称的由来。有了这个前提解题思路就变得清晰了。我们要解决的无非是“如何高效地从M条边里挑出那N-1条边”而两个最经典的选择策略一个是优先从权值最小的边开始看另一个是从某个节点开始不断向外扩展。这两条路分别对应Kruskal算法和Prim算法。1.3 两种贪心直觉恰好对应两个算法我在第一次做这道题的时候脑子里冒出来的第一个想法是先把所有边按照花费从低到高排个序然后从最小的边开始逐个尝试只要这条边能让当前图变得更连通就留下它。这个思路非常自然它就是Kruskal算法。第二种想法是随便选一个宝藏点作为起点先把通往最近邻点的路建上然后把已经连通的区域看成一个整体再从这片区域向外找最小花费的边不断“吞噬”新的点。这是Prim算法的思路。两种方式最终都能得到最优解但它们在实现层面依赖的数据结构完全不同。Kruskal依赖并查集来快速判断两个点是否已经连通Prim依赖优先队列最小堆来高效获取“当前可以扩展的最小边”。我在训练营前面的章节里学过并查集也刷过不少堆相关的题目但直到做这道“寻宝”题才真正体会到这两个工具的配合有多巧妙。2. Kruskal路线把边按权值排序用并查集完成连通块合并2.1 完整的算法主流程Kruskal算法的思想可以用一句话概括把所有边按权值从小到大排序然后依次尝试每条边如果这条边连接的两个节点已经连通就跳过否则就把它们连通并累加这条边的权值。选够N-1条边后算法结束。具体步骤拆开来看是这样读入全部N个节点和M条边把每条边存储为三元组权值w起点u终点v。对M条边按w从小到大排序。初始化并查集让每个节点独立成为一个集合。从小到大遍历每条边用并查集查询u和v是否在同一个集合中。如果不在同一个集合说明这条边可以安全地加入生成树执行合并操作并把w累加到答案里如果在同一个集合说明加入这条边会形成环直接丢弃。当已经选出N-1条边时提前停止遍历输出答案。这个流程里最关键的一步是第5步的“会形成环”判断。举个例子一个三角形有三条边权值分别是1、2、3。排序后先看权值1的边两个端点原来不连通加入再看权值2的边两个端点也不连通加入最后看权值3的边这时两个端点已经通过前两条边连通了加入就会形成环所以必须跳过。2.2 为什么“能要就要”的贪心不会出错很多人第一次学Kruskal时都会有个疑问只因为某条边权值最小就先选它万一这一步的局部最优破坏了全局最优怎么办这里需要一点理论支撑但不需要严格证明到数学论文的程度只需要理解交换论证的思想。假设存在一棵最优生成树T它没有选择某条权值较小的边e。把e加入T一定会形成一个环。在这个环上至少有一条边f的权值大于或等于e的权值。如果我们用e替换掉f得到的仍然是一棵生成树并且总权值不会增加甚至可能变小。这意味着任何“跳过这条最小边”的最优解都可以被换成“包含这条最小边”的最优解。逐条边做这样的替换就说明Kruskal的贪心选择不会错失最优解。这个论证不需要背下来但理解了它之后你会对贪心算法产生更踏实的信任感而不是“碰巧能过”的侥幸感。2.3 并查集的实现要点训练营知识点的实战检验Kruskal的代码主体并不长但并查集写得好不好直接影响提交成绩。我在训练营早期刷并查集专题时觉得路径压缩已经够了按秩合并无所谓。结果在“寻宝”这题的数据量下不写按秩合并也能过但如果数据再大一些退化风险就会暴露出来。稳妥起见我建议这里直接写完整版。int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } void unite(int a, int b) { a find(a); b find(b); if (a b) return; if (rank[a] rank[b]) swap(a, b); parent[b] a; if (rank[a] rank[b]) rank[a]; }路径压缩保证了find操作近似O(1)按秩合并保证了树的深度不会失控。两个一起用并查集的操作时间可以看作常数级别整个Kruskal算法的瓶颈只剩排序本身的O(E log E)。2.4 Kruskal的时间复杂度与应用场景Kruskal的复杂度主要由排序决定为O(E log E)其中E是边数。并查集部分可以近似看作O(E α(N))α(N)是反阿克曼函数增长极为缓慢。所以整体来讲Kruskal在边数较少时表现非常好适合稀疏图。在“寻宝”这道题里如果M和N的规模在同一数量级甚至M更小那无脑选Kruskal就可以了。它的另一个优点是实现直观不容易写错你只需要把边排序然后维护一个并查集逻辑链条非常短。3. Prim路线从任意点出发用优先队列贪心扩展连通块3.1 算法主流程与朴素的选点思路如果说Kruskal是从“边”的视角入手那么Prim就是从“点”的视角入手。它维护一个“已经加入生成树”的点集合初始时可以任选一个点加入。接下来反复执行这样的操作在连接树内点和树外点的所有边中找出权值最小的那条边把对应树外点加入树中并累加边权。重复N-1次之后所有点就都在树里了。最直白的实现方式是维护一个数组dist表示每个树外点连接到当前树的最小边权。每次扫描所有树外点找dist最小的那个加入树中然后更新它的邻接点。这个做法的时间复杂度是O(V^2)在稠密图里比如V只有几千但M很大时表现很好。但对于“寻宝”这类边数和点数都可能上万的情况我更倾向于用优先队列优化。它的做法是把“当前树可以向外扩展的所有边”都丢进一个小顶堆每次从堆顶取一条边如果边的另一端已经在树内就跳过否则就把这个新点加入树中并把这个新点的所有邻边也都丢进堆里。3.2 为什么任选起点都能得到最优解Prim算法给人最不直观的地方在于我随便选一个起点怎么保证最后得到的就是全局最优其实这个性质和Kruskal的证明思路殊途同归。无论你从哪个点开始当前树和剩余点之间的“割”上权值最小的那条边一定是某棵最小生成树中的边。因为如果有更优方案不使用这条跨割最小边就可以用交换论证把它替换进去而不会变差。正因为每次Prim都选择“当前割上的最小边”所以无论起始点是谁最终形成的生成树权值都一样大。这个“割性质”是理解Prim的关键也是后续学习次小生成树、瓶颈生成树时反复用到的基础。3.3 堆优化Prim的完整代码骨架用C实现堆优化Prim时我习惯用pair存储候选边第一个元素是权值第二个元素是端点编号。这样优先队列默认的小顶堆可以自动按权值排序。完整代码骨架如下#include bits/stdc.h using namespace std; using PII pairint, int; int main() { int n, m; cin n m; vectorvectorPII g(n 1); for (int i 0; i m; i) { int u, v, w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); } vectorint vis(n 1, 0); priority_queuePII, vectorPII, greaterPII pq; pq.push({0, 1}); long long ans 0; int cnt 0; while (!pq.empty()) { auto [w, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] 1; ans w; cnt; for (auto [v, ww] : g[u]) { if (!vis[v]) { pq.push({ww, v}); } } } if (cnt ! n) { cout 图不连通 endl; } else { cout ans endl; } return 0; }有几个细节需要特别注意。第一无向图建邻接表时必须双向存储我只存一边的话后面更新会漏边。第二优先队列里允许出现重复边因为一个点可能通过不同路径被推进堆多次但vis数组保证只有第一次弹出时才真正生效。第三答案要用long long如果边权和可能超过int范围用int会造成溢出这种错误在样例上很难发现提交后才会暴露。3.4 Prim的时间复杂度与适用场景堆优化Prim的复杂度是O((VE) log V)在大多数竞赛数据下都能轻松通过。它和Kruskal的取舍在于稠密图E接近V^2时朴素Prim的O(V^2)可能更快稀疏图时Kruskal更简单。对于“寻宝”这种没有明确给出稠密还是稀疏的题我更推荐先读题看数据范围如果N很小而M很大用Prim如果M和N同阶甚至M比N还小用Kruskal。这两者在“寻宝”的数据范围内都够用选择标准更多是个人编码习惯和是否能一遍写对。4. 可直接提交的C题解Kruskal与Prim的完整实现对照4.1 Kruskal版本的完整代码把前面的并查集和排序流程组合起来就是一份能直接跑的Kruskal题解。我用tuple存边排序时按权值优先排序这样代码读起来最舒服。#include bits/stdc.h using namespace std; const int MAXN 100005; int parent[MAXN], rk[MAXN]; int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } void unite(int a, int b) { a find(a); b find(b); if (a b) return; if (rk[a] rk[b]) swap(a, b); parent[b] a; if (rk[a] rk[b]) rk[a]; } int main() { int n, m; cin n m; vectortupleint, int, int edges; for (int i 0; i m; i) { int u, v, w; cin u v w; edges.push_back({w, u, v}); } sort(edges.begin(), edges.end()); for (int i 1; i n; i) { parent[i] i; rk[i] 0; } long long ans 0; int cnt 0; for (auto [w, u, v] : edges) { if (find(u) ! find(v)) { unite(u, v); ans w; cnt; if (cnt n - 1) break; } } if (cnt n - 1) { cout ans endl; } else { cout 图不连通 endl; } return 0; }这份代码我把“图不连通”的情况也处理了。最初我只写else输出ans乍一看没问题但如果在“寻宝”的测试数据里混入森林不连通图cnt到不了n-1程序会输出一个不完整的结果。虽然标准题意应该保证连通但养成判断连通性的习惯对你的面试代码和竞赛代码都有好处。4.2 两版代码的对比与选型建议我给出的Prim版本代码和Kruskal版本代码各有一些优势。Prim的代码里不需要并查集也不需要排序只是优先队列的语法要稍微熟悉一些Kruskal则几乎没有思维难度难点全在并查集是否扎实。如果让新手二选一我会建议第一遍写Kruskal因为它的步骤更线性不容易出现堆使用上的逻辑漏洞。但如果图特别稠密或者你确定数据规模大、内存紧那Prim的堆优化版本会更稳。这两份代码都是O(E log V)级别的复杂度在“寻宝”的数据范围内跑得飞快。4.3 必测的三个小样例我每次写完最小生成树代码都会先测下面三个小样例跑通了再提交。这几个样例能覆盖绝大部分常见错误。第一个是链式图4个点3条边分别是1-2权值1、2-3权值1、3-4权值1。答案显然是3此时Kruskal会依次选3条边Prim从任意点开始也恰好选3条边。这个样例主要验证基本流程。第二个是三角形图3个点3条边1-2权值1、2-3权值2、1-3权值3。答案应该是3选1-2和2-3。Kruskal排序后会先选1、2再选2、3然后跳过1-3Prim从1开始选1-2再从堆中弹出2-3。这个样例能检查你是否正确处理了“成环跳过”和“去重访问”。第三个是带自环和重边的图比如3个点之间有三条1-2权值2的边再加一条1-1权值100的自环。正确输出应该为4选一条1-2权值2一条2-3权值2自环忽略。这个样例能暴露两个问题自环是否会导致Prim误算重边是否会干扰Kruskal的合并判断。实际上只要用了vis数组和并查集自环会被天然跳过重边只会让堆中多几个候选但不影响最终结果。4.4 提交前的一处关键自查我犯过的一个很低级的错误是忘了把答案累加部分放在正确的位置。Prim里我曾在if (vis[u]) continue之前就执行ans w导致同一个点被访问两次时权值被重复计算。这类问题的排查方法很简单就是在每一个样例里手工模拟一次把每一步弹出的边写下来对照程序输出是否一致。如果样例太小不够完全可以构造一个5点、6边、带3条重边的输入手工算一遍答案再用程序跑一遍。这个过程虽然花时间但能避免提交后反复WA的挫败感。5. 训练营第六十二天的位置MST是图论、并查集、贪心的汇合点5.1 走到这一天时你回头看会看到什么代码随想录训练营的图论部分不是孤立存在的。到第六十二天时前面已经铺垫了大量基础DFS、BFS、深搜去重、拓扑排序、最短路径Dijkstra、Bellman-Ford、Floyd还有独立的并查集专题。最小生成树恰好是把这些知识拧成一股绳的题目类型。Kruskal用到的是并查集加贪心Prim用到的是图存储加堆两种解法都在反复考验一个核心能力把题目里的条件抽象成图模型再把图模型对应到一块熟悉的数据结构。这正好呼应了卡码网这道“寻宝”题的命名——表面上是在寻宝实际上是在寻找“如何用最少的代价把所有节点连成一张网”的建模直觉。5.2 对“寻宝”这类应用题的建模建议还有一点值得多说一句训练营的题目经常把算法藏在生活化场景里。“寻宝”是把修路问题包装成藏宝图“修水管”“架电线”“建通信基站”也都是同一类包装。你在读题时应当训练自己快速剥离场景找到“N个点、M条带权边、求最小连通代价”这个骨架。这种抽象能力不只是为了这道题更是为了应对真实面试里的系统设计题和算法题——很多问题最终都会归结到一个经典模型上。5.3 做完这题之后可以继续想的几个方向如果你把“寻宝”AC之后还有余力我建议思考三个问题。第一个问题如果题目中某些边是单向的还能直接用最小生成树算法吗答案是不能因为MST的定义建立在无向图上有向图的对应问题是“最小树形图”需要用朱刘算法这已经是另一个知识块了。第二个问题如果题目不保证图连通要求输出“无法连通”代码应该怎么改这个我在上面的代码里已经顺手写了核心就是cnt是否等于n或n-1的判断。第三个问题如果不仅要求最小总花费还要求输出一种具体的选边方案Kruskal应该怎么记录答案方法很简单在每次成功合并时把当前边存入一个vector最后输出即可。这在实际工程中比只输出一个数字更有意义因为它能告诉你“路到底该怎么修”。5.4 我个人的练习建议第六十二天这道题我的建议是你至少亲手把Kruskal和Prim各写一遍。不是说考试会考两遍而是这两套代码的思维模式完全不同。Kruskal强迫你理解“边排序、并查集合并”的离线思考方式Prim强迫你熟悉“visited数组、优先队列、邻接表更新”的在线扩展方式。两种都写过了你对最小生成树的理解才会真正立体起来而不是停留在“背模板”的层面。我最终提交“寻宝”的时候用的是堆优化Prim因为自己写Kruskal时总觉得并查集已经练过太多遍想换个姿势提升一下对堆的熟练度。但改天遇到数据量很大的稠密图我可能会切回Kruskal或者朴素Prim毕竟“能用且不复杂”才是竞赛和工作中更重要的原则。最后分享一个小技巧不管用哪个算法提交之前一定要伪造几个极限数据比如N100000、M100000权值给到1e9。看看自己的代码会不会因为vector频繁扩容而超时或者因为long long用法不统一而出现编译警告。这种极限测试我在训练营里养成习惯之后后面的图论题基本都是一次AC的概率更大省下的时间远比写测试代码的时间多。
寻宝题解：最小生成树Kruskal与Prim算法完整实现
到了训练营第六十二天卡码网KamaCoder53这道“寻宝”题我前后提交了四次才算彻底跑通。不是题本身有多难而是我一开始把它当成最短路去想了绕了好大一圈才意识到题目里说的“打通所有藏宝点之间的道路让任意两点都能相互到达并且总花费最小”这正是教科书级的最小生成树问题。如果你也正卡在这道题上或者刚做完想回头捋一捋Kruskal和Prim的差异那这篇文章应该能给你一些实在的参考。先说结论KamaCoder53“寻宝”本质上是一道无向带权图的最小生成树题。图里有N个节点M条边每条边有一个花费你需要选择其中一部分边让所有节点连通且选出的边的总花费最小。约束条件没有特别刁钻的地方数据范围也适合用常规的Kruskal或堆优化Prim去做。真正值得琢磨的是为什么这个问题不能用最短路思路为什么最终答案一定是一棵树以及两种主流解法各自适合什么场景。这些内容我会在后面逐段展开顺手把可直接提交的C代码和调试样例也贴出来。1. 题面拆解为什么“寻宝”是所有点连通的最小花费问题1.1 从一个朴素的连通需求说起这道题的场景包装很有意思你有一张藏宝图图上散布着若干个宝藏点点与点之间有一些已经存在的道路每条道路的修建或通行成本不同。你的目标是让任意一个宝藏点都能通过若干条道路到达其他所有宝藏点求满足条件的最小总成本。这个描述里藏着两个容易忽略的关键词。第一个是“任意两点都能到达”这意味着我们的目标不是从A点到B点的某一条路径最短而是整个图作为一个整体必须连通。第二个是“总成本最小”也就是说我们要在保证连通的前提下把选中的边权之和压到最低。这两个条件组合在一起定义了一个和“最短路”完全不同的优化目标。打个比方最短路问题像你在城市里叫网约车只想从家到公司距离最短一路上经过哪些路口根本不重要而最小生成树问题像电信运营商在几个城市之间拉骨干光缆目标是让所有城市都接入这张网络至于某两个城市之间的绕行距离是多少反而不是首要考虑。这两类问题表面上都涉及“选边”和“权值”但优化的对象完全不同。1.2 生成树为什么最优方案一定没有环明确了目标是“全连通”之后一个自然的追问是最终选出的边会是什么形态假设图里有N个节点如果选择的结果包含了一个环那么去掉环上的任意一条边原来连通的节点依然连通而总成本却变小了。既然我们要的是最小成本那么任何带环的方案都必然不是最优解。所以最优方案一定是一个无环连通图也就是一棵生成树。连通N个节点至少需要N-1条边而一棵树恰好有N-1条边。所以这道题的答案必然是从M条边中选出N-1条边构成一棵生成树并且让这棵生成树的总权值最小。这就是“最小生成树”这个名称的由来。有了这个前提解题思路就变得清晰了。我们要解决的无非是“如何高效地从M条边里挑出那N-1条边”而两个最经典的选择策略一个是优先从权值最小的边开始看另一个是从某个节点开始不断向外扩展。这两条路分别对应Kruskal算法和Prim算法。1.3 两种贪心直觉恰好对应两个算法我在第一次做这道题的时候脑子里冒出来的第一个想法是先把所有边按照花费从低到高排个序然后从最小的边开始逐个尝试只要这条边能让当前图变得更连通就留下它。这个思路非常自然它就是Kruskal算法。第二种想法是随便选一个宝藏点作为起点先把通往最近邻点的路建上然后把已经连通的区域看成一个整体再从这片区域向外找最小花费的边不断“吞噬”新的点。这是Prim算法的思路。两种方式最终都能得到最优解但它们在实现层面依赖的数据结构完全不同。Kruskal依赖并查集来快速判断两个点是否已经连通Prim依赖优先队列最小堆来高效获取“当前可以扩展的最小边”。我在训练营前面的章节里学过并查集也刷过不少堆相关的题目但直到做这道“寻宝”题才真正体会到这两个工具的配合有多巧妙。2. Kruskal路线把边按权值排序用并查集完成连通块合并2.1 完整的算法主流程Kruskal算法的思想可以用一句话概括把所有边按权值从小到大排序然后依次尝试每条边如果这条边连接的两个节点已经连通就跳过否则就把它们连通并累加这条边的权值。选够N-1条边后算法结束。具体步骤拆开来看是这样读入全部N个节点和M条边把每条边存储为三元组权值w起点u终点v。对M条边按w从小到大排序。初始化并查集让每个节点独立成为一个集合。从小到大遍历每条边用并查集查询u和v是否在同一个集合中。如果不在同一个集合说明这条边可以安全地加入生成树执行合并操作并把w累加到答案里如果在同一个集合说明加入这条边会形成环直接丢弃。当已经选出N-1条边时提前停止遍历输出答案。这个流程里最关键的一步是第5步的“会形成环”判断。举个例子一个三角形有三条边权值分别是1、2、3。排序后先看权值1的边两个端点原来不连通加入再看权值2的边两个端点也不连通加入最后看权值3的边这时两个端点已经通过前两条边连通了加入就会形成环所以必须跳过。2.2 为什么“能要就要”的贪心不会出错很多人第一次学Kruskal时都会有个疑问只因为某条边权值最小就先选它万一这一步的局部最优破坏了全局最优怎么办这里需要一点理论支撑但不需要严格证明到数学论文的程度只需要理解交换论证的思想。假设存在一棵最优生成树T它没有选择某条权值较小的边e。把e加入T一定会形成一个环。在这个环上至少有一条边f的权值大于或等于e的权值。如果我们用e替换掉f得到的仍然是一棵生成树并且总权值不会增加甚至可能变小。这意味着任何“跳过这条最小边”的最优解都可以被换成“包含这条最小边”的最优解。逐条边做这样的替换就说明Kruskal的贪心选择不会错失最优解。这个论证不需要背下来但理解了它之后你会对贪心算法产生更踏实的信任感而不是“碰巧能过”的侥幸感。2.3 并查集的实现要点训练营知识点的实战检验Kruskal的代码主体并不长但并查集写得好不好直接影响提交成绩。我在训练营早期刷并查集专题时觉得路径压缩已经够了按秩合并无所谓。结果在“寻宝”这题的数据量下不写按秩合并也能过但如果数据再大一些退化风险就会暴露出来。稳妥起见我建议这里直接写完整版。int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } void unite(int a, int b) { a find(a); b find(b); if (a b) return; if (rank[a] rank[b]) swap(a, b); parent[b] a; if (rank[a] rank[b]) rank[a]; }路径压缩保证了find操作近似O(1)按秩合并保证了树的深度不会失控。两个一起用并查集的操作时间可以看作常数级别整个Kruskal算法的瓶颈只剩排序本身的O(E log E)。2.4 Kruskal的时间复杂度与应用场景Kruskal的复杂度主要由排序决定为O(E log E)其中E是边数。并查集部分可以近似看作O(E α(N))α(N)是反阿克曼函数增长极为缓慢。所以整体来讲Kruskal在边数较少时表现非常好适合稀疏图。在“寻宝”这道题里如果M和N的规模在同一数量级甚至M更小那无脑选Kruskal就可以了。它的另一个优点是实现直观不容易写错你只需要把边排序然后维护一个并查集逻辑链条非常短。3. Prim路线从任意点出发用优先队列贪心扩展连通块3.1 算法主流程与朴素的选点思路如果说Kruskal是从“边”的视角入手那么Prim就是从“点”的视角入手。它维护一个“已经加入生成树”的点集合初始时可以任选一个点加入。接下来反复执行这样的操作在连接树内点和树外点的所有边中找出权值最小的那条边把对应树外点加入树中并累加边权。重复N-1次之后所有点就都在树里了。最直白的实现方式是维护一个数组dist表示每个树外点连接到当前树的最小边权。每次扫描所有树外点找dist最小的那个加入树中然后更新它的邻接点。这个做法的时间复杂度是O(V^2)在稠密图里比如V只有几千但M很大时表现很好。但对于“寻宝”这类边数和点数都可能上万的情况我更倾向于用优先队列优化。它的做法是把“当前树可以向外扩展的所有边”都丢进一个小顶堆每次从堆顶取一条边如果边的另一端已经在树内就跳过否则就把这个新点加入树中并把这个新点的所有邻边也都丢进堆里。3.2 为什么任选起点都能得到最优解Prim算法给人最不直观的地方在于我随便选一个起点怎么保证最后得到的就是全局最优其实这个性质和Kruskal的证明思路殊途同归。无论你从哪个点开始当前树和剩余点之间的“割”上权值最小的那条边一定是某棵最小生成树中的边。因为如果有更优方案不使用这条跨割最小边就可以用交换论证把它替换进去而不会变差。正因为每次Prim都选择“当前割上的最小边”所以无论起始点是谁最终形成的生成树权值都一样大。这个“割性质”是理解Prim的关键也是后续学习次小生成树、瓶颈生成树时反复用到的基础。3.3 堆优化Prim的完整代码骨架用C实现堆优化Prim时我习惯用pair存储候选边第一个元素是权值第二个元素是端点编号。这样优先队列默认的小顶堆可以自动按权值排序。完整代码骨架如下#include bits/stdc.h using namespace std; using PII pairint, int; int main() { int n, m; cin n m; vectorvectorPII g(n 1); for (int i 0; i m; i) { int u, v, w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); } vectorint vis(n 1, 0); priority_queuePII, vectorPII, greaterPII pq; pq.push({0, 1}); long long ans 0; int cnt 0; while (!pq.empty()) { auto [w, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] 1; ans w; cnt; for (auto [v, ww] : g[u]) { if (!vis[v]) { pq.push({ww, v}); } } } if (cnt ! n) { cout 图不连通 endl; } else { cout ans endl; } return 0; }有几个细节需要特别注意。第一无向图建邻接表时必须双向存储我只存一边的话后面更新会漏边。第二优先队列里允许出现重复边因为一个点可能通过不同路径被推进堆多次但vis数组保证只有第一次弹出时才真正生效。第三答案要用long long如果边权和可能超过int范围用int会造成溢出这种错误在样例上很难发现提交后才会暴露。3.4 Prim的时间复杂度与适用场景堆优化Prim的复杂度是O((VE) log V)在大多数竞赛数据下都能轻松通过。它和Kruskal的取舍在于稠密图E接近V^2时朴素Prim的O(V^2)可能更快稀疏图时Kruskal更简单。对于“寻宝”这种没有明确给出稠密还是稀疏的题我更推荐先读题看数据范围如果N很小而M很大用Prim如果M和N同阶甚至M比N还小用Kruskal。这两者在“寻宝”的数据范围内都够用选择标准更多是个人编码习惯和是否能一遍写对。4. 可直接提交的C题解Kruskal与Prim的完整实现对照4.1 Kruskal版本的完整代码把前面的并查集和排序流程组合起来就是一份能直接跑的Kruskal题解。我用tuple存边排序时按权值优先排序这样代码读起来最舒服。#include bits/stdc.h using namespace std; const int MAXN 100005; int parent[MAXN], rk[MAXN]; int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } void unite(int a, int b) { a find(a); b find(b); if (a b) return; if (rk[a] rk[b]) swap(a, b); parent[b] a; if (rk[a] rk[b]) rk[a]; } int main() { int n, m; cin n m; vectortupleint, int, int edges; for (int i 0; i m; i) { int u, v, w; cin u v w; edges.push_back({w, u, v}); } sort(edges.begin(), edges.end()); for (int i 1; i n; i) { parent[i] i; rk[i] 0; } long long ans 0; int cnt 0; for (auto [w, u, v] : edges) { if (find(u) ! find(v)) { unite(u, v); ans w; cnt; if (cnt n - 1) break; } } if (cnt n - 1) { cout ans endl; } else { cout 图不连通 endl; } return 0; }这份代码我把“图不连通”的情况也处理了。最初我只写else输出ans乍一看没问题但如果在“寻宝”的测试数据里混入森林不连通图cnt到不了n-1程序会输出一个不完整的结果。虽然标准题意应该保证连通但养成判断连通性的习惯对你的面试代码和竞赛代码都有好处。4.2 两版代码的对比与选型建议我给出的Prim版本代码和Kruskal版本代码各有一些优势。Prim的代码里不需要并查集也不需要排序只是优先队列的语法要稍微熟悉一些Kruskal则几乎没有思维难度难点全在并查集是否扎实。如果让新手二选一我会建议第一遍写Kruskal因为它的步骤更线性不容易出现堆使用上的逻辑漏洞。但如果图特别稠密或者你确定数据规模大、内存紧那Prim的堆优化版本会更稳。这两份代码都是O(E log V)级别的复杂度在“寻宝”的数据范围内跑得飞快。4.3 必测的三个小样例我每次写完最小生成树代码都会先测下面三个小样例跑通了再提交。这几个样例能覆盖绝大部分常见错误。第一个是链式图4个点3条边分别是1-2权值1、2-3权值1、3-4权值1。答案显然是3此时Kruskal会依次选3条边Prim从任意点开始也恰好选3条边。这个样例主要验证基本流程。第二个是三角形图3个点3条边1-2权值1、2-3权值2、1-3权值3。答案应该是3选1-2和2-3。Kruskal排序后会先选1、2再选2、3然后跳过1-3Prim从1开始选1-2再从堆中弹出2-3。这个样例能检查你是否正确处理了“成环跳过”和“去重访问”。第三个是带自环和重边的图比如3个点之间有三条1-2权值2的边再加一条1-1权值100的自环。正确输出应该为4选一条1-2权值2一条2-3权值2自环忽略。这个样例能暴露两个问题自环是否会导致Prim误算重边是否会干扰Kruskal的合并判断。实际上只要用了vis数组和并查集自环会被天然跳过重边只会让堆中多几个候选但不影响最终结果。4.4 提交前的一处关键自查我犯过的一个很低级的错误是忘了把答案累加部分放在正确的位置。Prim里我曾在if (vis[u]) continue之前就执行ans w导致同一个点被访问两次时权值被重复计算。这类问题的排查方法很简单就是在每一个样例里手工模拟一次把每一步弹出的边写下来对照程序输出是否一致。如果样例太小不够完全可以构造一个5点、6边、带3条重边的输入手工算一遍答案再用程序跑一遍。这个过程虽然花时间但能避免提交后反复WA的挫败感。5. 训练营第六十二天的位置MST是图论、并查集、贪心的汇合点5.1 走到这一天时你回头看会看到什么代码随想录训练营的图论部分不是孤立存在的。到第六十二天时前面已经铺垫了大量基础DFS、BFS、深搜去重、拓扑排序、最短路径Dijkstra、Bellman-Ford、Floyd还有独立的并查集专题。最小生成树恰好是把这些知识拧成一股绳的题目类型。Kruskal用到的是并查集加贪心Prim用到的是图存储加堆两种解法都在反复考验一个核心能力把题目里的条件抽象成图模型再把图模型对应到一块熟悉的数据结构。这正好呼应了卡码网这道“寻宝”题的命名——表面上是在寻宝实际上是在寻找“如何用最少的代价把所有节点连成一张网”的建模直觉。5.2 对“寻宝”这类应用题的建模建议还有一点值得多说一句训练营的题目经常把算法藏在生活化场景里。“寻宝”是把修路问题包装成藏宝图“修水管”“架电线”“建通信基站”也都是同一类包装。你在读题时应当训练自己快速剥离场景找到“N个点、M条带权边、求最小连通代价”这个骨架。这种抽象能力不只是为了这道题更是为了应对真实面试里的系统设计题和算法题——很多问题最终都会归结到一个经典模型上。5.3 做完这题之后可以继续想的几个方向如果你把“寻宝”AC之后还有余力我建议思考三个问题。第一个问题如果题目中某些边是单向的还能直接用最小生成树算法吗答案是不能因为MST的定义建立在无向图上有向图的对应问题是“最小树形图”需要用朱刘算法这已经是另一个知识块了。第二个问题如果题目不保证图连通要求输出“无法连通”代码应该怎么改这个我在上面的代码里已经顺手写了核心就是cnt是否等于n或n-1的判断。第三个问题如果不仅要求最小总花费还要求输出一种具体的选边方案Kruskal应该怎么记录答案方法很简单在每次成功合并时把当前边存入一个vector最后输出即可。这在实际工程中比只输出一个数字更有意义因为它能告诉你“路到底该怎么修”。5.4 我个人的练习建议第六十二天这道题我的建议是你至少亲手把Kruskal和Prim各写一遍。不是说考试会考两遍而是这两套代码的思维模式完全不同。Kruskal强迫你理解“边排序、并查集合并”的离线思考方式Prim强迫你熟悉“visited数组、优先队列、邻接表更新”的在线扩展方式。两种都写过了你对最小生成树的理解才会真正立体起来而不是停留在“背模板”的层面。我最终提交“寻宝”的时候用的是堆优化Prim因为自己写Kruskal时总觉得并查集已经练过太多遍想换个姿势提升一下对堆的熟练度。但改天遇到数据量很大的稠密图我可能会切回Kruskal或者朴素Prim毕竟“能用且不复杂”才是竞赛和工作中更重要的原则。最后分享一个小技巧不管用哪个算法提交之前一定要伪造几个极限数据比如N100000、M100000权值给到1e9。看看自己的代码会不会因为vector频繁扩容而超时或者因为long long用法不统一而出现编译警告。这种极限测试我在训练营里养成习惯之后后面的图论题基本都是一次AC的概率更大省下的时间远比写测试代码的时间多。