1. 从最短路径到最小生成树第57天的学习坐标今天已经是训练营第五十七天。前两周我们一直在围着图论转一口气刷完了深度优先遍历、广度优先遍历、拓扑排序、最短路径系列好不容易觉得自己和图熟了结果今天的两节课直接把我拉回原来我对图的理解还很浅的状态。今天的内容是往最小生成树方向走的精讲部分的重点是Prim算法和Kruskal算法。坦白说刚看到课表的时候我有点困惑。最短路径解决的是从A点到B点怎么走最近最小生成树解决的问题却是怎么用最少的边让整张图连通两个问题听起来接近实际目标完全不同。我一开始甚至觉得最小生成树没什么用直到跟着精讲里案例一步步推完才意识到它在网络规划、集群设计、电路布线这类场景里有多常见。这篇文章不是我抄讲义整理的笔记而是我把今天课程里的两个算法揉碎、重新用自己方式表达出来的学习复盘。适合两类读者一类是和我一样正在按训练营节奏刷图论的初学者另一类是已经知道这两个算法名字、但始终没搞懂为什么得这么写的读者。我会直接讲原理、给模板、写复杂度也会把今天我踩过的坑和想通的关键点都放进去。先立住一个基本认知什么叫生成树一个连通的无向图如果挑出一部分边让所有节点依然连通并且不形成任何环那这部分边和全部节点一起就构成一棵树。因为边数等于节点数减一所以这棵树能覆盖所有顶点。在满足这个条件的所有树里边的权重和最小的那棵就是最小生成树。接下来所有讨论都是围绕找到这棵树展开的。2. Prim算法精讲把已经连好的部分当作一个大节点2.1 从一个起点开始像滚雪球一样扩张Prim算法的核心思想我记得课程里的说法是从一个顶点出发逐步扩大生成树的顶点集合。我自己的理解更直白把已经纳入最小生成树的那些节点想象成一个超级大节点每次从这个超级节点和外面的节点之间挑一条最短的边把边另一边的新节点吞进来重复直到所有节点都在超级节点里。这个过程是不是听起来很眼熟如果你刷过Dijkstra会发现Prim在每一步选一个最小的东西这个节奏上和Dijkstra有点像。但两者的更新逻辑有本质区别Dijkstra维护的是某个起点到各个节点的最短距离Prim维护的是整个已选节点集合到各个未选节点的最小连接代价。也就是说Dijkstra里每个节点只有一个起点维度的距离Prim里每个节点的距离会随着集合扩张而动态变成离集合里任意节点最近的那条边的权值。我用一个很简单的例子来推演。假设有4个节点1号节点和2号节点之间权值为12号和3号之间权值为33号和4号之间权值为41号和4号之间权值为52号和4号之间权值为2。从1号开始已选集合是{1}这时1到2的权值是11到4的权值是5选最小的边是1-2把2加进来。现在已选集合是{1,2}对3号来说从它到已选集合最近的边是2-3权值3对4号来说从它到已选集合最近的边是2-4权值2比原先的1-4权值5更小所以更新。于是现在找最小的未选节点连接代价2号到4号是21号到4号是5所以选4号进来最后剩下3号最近的边是3-4权值4。整棵树的边就是1-2、2-4、3-4总代价7。我把这个例子在手写纸上画了三遍才彻底明白更新的是到集合的距离这句话。2.2 为什么贪心在这里不会失效今天最大的一个思想障碍就是每一步都贪心地选最小边真的能保证最后全局最小课程里给了一个非常扎实的论证我想用自己的话复述一遍。假设当前已选集合叫S剩余节点叫T。我们要找一条跨越S和T的边。如果当前选的是从S到T权值最小的一条边e那么在所有可能的最终最小生成树里至少有一棵树是包含e的。原因可以用切断边互换来证明假如有一棵最小生成树不包含e那它一定有一条别的跨过S和T的边f。把e加进这棵树会形成一个环环里必然包含f如果把f去掉、把e放回去整棵树依然连通且边数不变但总权值不会变大因为e的权值小于等于f。所以保留e不会丢掉全局最优解。这个证明我一开始绕了很久关键在于至少有一棵最优解包含这条边而不是每一步都必须包含这条边。贪心算法不需要保证每一步都走在唯一的最优路线上只要保证当前选择能被某个全局最优解兼容然后一路走下去最后得到的局部选择集合就是完整的全局最优解。Prim的每一步选的都不是最短的一条边而是跨边界的最短边这个边界会不断外扩所以证明了每个局部决策都有存在最优解的兼容性。想通这一点再看代码理解会猛然深一层。2.3 朴素Prim的完整模板和复杂度拆解下面这个模板是我今天按照课程思路整理出来的使用邻接矩阵存图适合节点数比较少、图比较稠密的场景。我用Python写出来细节处都加了注释import sys def prim(n, graph): # graph[i][j] 表示 i 到 j 的边权不连通设为 INF INF 10 ** 9 visited [False] * n # lowcost[j] 表示 j 到当前已选集合的最小边权 lowcost [INF] * n lowcost[0] 0 total 0 parent [-1] * n # 记录边从哪里来方便还原树结构 for _ in range(n): # 找出当前未选节点中 lowcost 最小的节点 u -1 min_cost INF for j in range(n): if not visited[j] and lowcost[j] min_cost: min_cost lowcost[j] u j if u -1: return None # 图不连通不存在生成树 visited[u] True total min_cost # 用新加入的节点 u 去更新其他未选节点的 lowcost for v in range(n): if not visited[v] and graph[u][v] lowcost[v]: lowcost[v] graph[u][v] parent[v] u return total, parent if __name__ __main__: n 4 graph [[0, 1, 10**9, 5], [1, 0, 3, 2], [10**9, 3, 0, 4], [5, 2, 4, 0]] res, parent prim(n, graph) print(res) # 输出 7复杂度方面外层循环执行n次每次找最小lowcost的过程需要遍历n个节点内层更新也要遍历n个节点所以朴素版的时间复杂度是O(n²)。空间上lowcost数组和visited数组各占O(n)邻接矩阵占O(n²)。对于稠密图O(n²)是很划算的但如果图是稀疏的尤其边数接近顶点的量级时这个复杂度就显得吃力了。2.4 为什么训练营先讲Prim而不是Kruskal我猜测课程顺序安排是有用意的。Prim更适合在邻接矩阵上讲解因为它的核心动作是找集合边界上的最小边而邻接矩阵天然支持快速访问任意一条边。同时Prim和Dijkstra的代码结构高度相似先讲Prim可以巩固前几天的Dijkstra理解让从一个点出发逐步扩展的思路在最短路径和最小生成树两个问题上形成对照。今天边听课边把两个模板并排看确实能发现许多共通的骨架都是维护一个visited数组都有一个不断更新的代价数组都有一个每轮取最小值的循环。只是更新语义不同一个关注到源点的最短距离一个关注到已选集合的最小边权。3. Kruskal算法精讲排序之后的并查集舞台3.1 把所有边拉出来排队从最小的开始挑如果说Prim是从点往外长Kruskal就是从边直接挑。Kruskal的思路非常朴素把图中所有边按权值从小到大排序然后依次考察每条边如果这条边连接的两个顶点目前还不在一棵子树里就把它选进生成树如果已经在同一棵树里说明加入这条边会形成环直接跳过。重复直到选满n-1条边。这个是否在同一棵树里的判断就是并查集的经典应用场景。并查集支持两种操作查找某个节点属于哪个集合合并两个集合。在Kruskal里我们利用并查集维护当前哪些点已经连通成块。判断一条边的两个端点是否在同一个集合只需要两次find如果不在union一下把两个集合合并。3.2 为什么Kruskal的贪心也是对的Kruskal的贪心正确性可以用一个和Prim类似但切入点不同的环性质来理解。最小生成树有一个著名的性质对于图中的任意一个环环上权值最大的边一定不属于任何一棵最小生成树只要有更小的替代边存在它就不可能出现在最优解里。Kruskal每次从小到大取边如果某条边会形成环说明在当前已经选出的若干条边中已经有一条路径连接了这条边的两端。由于我们是按权值从小到大处理的这条路径上的每条边的权值都小于等于当前边所以当前边就是这个环上最大的边应当被舍弃。这个证明我花了一点时间才转过弯关键在于理解环上最大的边会被淘汰这个性质。Kruskal用排序保证了每次遇到环时当前边一定是环上最晚出现的、至少不小于环上其他边的边所以淘汰它是安全的。这个思路和Prim的切断互换完全不同但都保证了全局最优。3.3 并查集模板与Kruskal完整实现今天写的Kruskal模板里我额外把并查集的路径压缩和按秩合并都加上了因为这两项优化能让并查集的操作近乎常数级别从而让整个算法的时间复杂度主要由排序决定。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.sort(keylambda x: x[2]) # 每条边表示为(u, v, w) dsu DSU(n) total 0 cnt 0 tree_edges [] for u, v, w in edges: if dsu.union(u, v): total w cnt 1 tree_edges.append((u, v, w)) if cnt n - 1: break if cnt ! n - 1: return None # 无法生成树图不连通 return total, tree_edges时间复杂度上排序是O(mlog m)m为边数。并查集操作在路径压缩和按秩合并下近似O(1)所以整体复杂度可以按排序复杂度来估算。空间复杂度主要是存储边列表的O(m)以及并查集的O(n)。3.4 今天在并查集细节上踩的一个坑课上练习时我在union的写法上踩了个坑。一开始我的union只是简单地把一个根的parent指向另一个根没有处理rank也没有比较两棵子树的高度。测试小图没问题数据一到几千个节点、边几乎每个案例都慢了不少。后来我把路径压缩和按秩合并补上速度才恢复正常。原因其实很简单如果union随意连并查集的树可能退化成链find操作会一路追到很长导致整体复杂度退化。这个问题在Kruskal里尤其明显因为算法全程都在反复调用find并查集的效率直接影响整体成绩。还有一个更隐蔽的坑我在实现find时一开始用的是递归在超过十万条边的案例里直接爆了Python默认递归深度。换成迭代写法之后问题就消失了。如果读者也喜欢用递归写find最好注意设置sys.setrecursionlimit但说实话迭代版更稳既然能顺手写迭代就别给递归留风险。4. 两种算法的选型对比稠密图与稀疏图的取舍逻辑4.1 一张表看清差异今天训练营把两个算法放在一起讲我觉得最有用的环节就是对比它们适用场景。我用一张表整理了核心差异方便读者直接抓住选型的判断依据对比维度Prim算法朴素版Kruskal算法图存储方式适合邻接矩阵适合边列表时间复杂度O(n²)O(mlog m)适用图类型稠密图m接近n²稀疏图m接近n核心数据结构visited数组、lowcost数组并查集贪心角度从顶点集合扩张出发从边权排序出发是否依赖排序否是处理非连通图会在循环中找不到可选节点会因边数不足n-1而返回None这里的n是顶点数m是边数。稠密图里m约等于n²那么Kruskal的复杂度为O(n²log n)而Prim朴素版是O(n²)常数更小稀疏图里m约等于nKruskal的复杂度为O(nlog n)而Prim仍然要O(n²)所以Kruskal优势明显。4.2 我选型时的思考顺序今天在做课后题时我总结了一套自己的判断顺序先看顶点数和边数哪个量级更高。如果顶点数量很少比如n只有几十那么怎么选都无所谓直接用自己最熟的模板就行。如果n很大再看边数m当m小于nlog n的量级时优先Kruskal因为排序成本低并查集接近线性当m接近n²时邻接矩阵版的Prim反而更容易写出低复杂度的实现。另一个判断角度是看输入数据格式。很多实际问题里数据给的是边列表那么写Kruskal几乎不需要额外转换直接排序即可如果数据给的是邻接矩阵或者边权矩阵天然存在Prim更顺手。这个选择会受到输入格式的强烈影响考试或者刷题时可以把这个当成重要依据。4.3 堆优化Prim的提升空间课程里提到朴素Prim适合稠密图但到了稀疏图除了Kruskal之外Prim也可以用堆优化来拯救。堆优化Prim的思路是把每次找最小lowcost这件事交给优先队列。每次从堆里弹出当前离集合最近的点然后用它去更新周围节点把更小的候选权值再次入堆。这样时间复杂度可以从O(n²)优化到O(mlog n)因为每条边最多被用来更新一次。我整理了一个堆优化Prim的简易版本供读者参考import heapq def prim_heap(n, graph): # graph 为邻接表: graph[i] [(j, w), ...] visited [False] * n heap [(0, 0)] # (cost, node)从节点0开始 total 0 cnt 0 while heap and cnt n: cost, u heapq.heappop(heap) if visited[u]: continue visited[u] True total cost cnt 1 for v, w in graph[u]: if not visited[v]: heapq.heappush(heap, (w, v)) if cnt ! n: return None return total这里有个容易误解的点堆里的元素即使后来被发现不是最优也不会被主动删掉只能靠visited来跳过所以堆的大小可能比n大不少。但实际运行中堆中的很多过期条目会被快速跳过总体效率依然可观。堆优化Prim在边稀疏、但依然想用Prim思路时很有效。4.4 选型时要考虑的隐藏因素除了复杂度今天让我意外的是选型还会受到边权相同时的稳定性影响。Kruskal在边权相等时选择的边的具体集合取决于排序后的稳定顺序但是最小生成树的权重和不会变Prim在边权相同时选哪个邻居也不会影响总权重。无论选哪棵总权重是一样的所以从做题角度不用担心输出边的顺序。但如果是实际工程有时会希望生成树的形态尽量平衡这时可以考虑在排序里加入按节点编号的次级排序或者让Prim的遍历顺序有确定性。还有一个容易被忽视的因素如果输入图本身就是非连通的两个算法的表现不同。Prim循环结束时会发现还剩节点没访问应该返回不存在Kruskal结束时会发现边数不够n-1也应该返回不存在。今天刷题时有道题我忘了判断非连通直接按默认值打印结果答案错误。这是最小生成树问题里最常见的低级失误值得单独提醒。5. 模板之外的细节环判断、无穷大与输入边界5.1 邻接矩阵里INF的设定要谨慎Prim的邻接矩阵会遇到一个实际问题不存在的边权用什么表示如果用一个特别大的数比如10⁹那么要注意相加时不会溢出或者在更新lowcost时要明确判断。我一开始犯过错误把不连通边的权值设为0结果Prim会把不存在的边当成权值0的边选进去。正确的做法是设成一个大数并确保大数大于所有真实边权之和这样才能保证不会选它。如果顶点数很多、边权也可能很大建议用类似10**18的值。非连通图场景更要注意如果某个节点和其他节点完全没有边lowcost[i]会一直是INF选点时min_cost也是INF此时u会等于-1要立刻返回不存在生成树。这个判断在训练营的例题中经常被隐藏很多同学因为没有及时判断而超时或者报错。5.2 Kruskal里的并查集需要注意自环和重边自环就是i到i的边。在Kruskal里自环的union一定返回False因为find(i)和find(i)本身相同所以会被直接跳过逻辑上没问题。但重边要注意如果两条边连接同一对节点但权值不同排序后只会先选小的后面那条遇到时会发现两个点已经连通直接跳过。所以Kruskal天然能正确处理重边不需要预处理去重。在Prim里如果邻接矩阵存的是最小边的权值那重边也不会有问题因为prim只关注最小值。但是如果邻接矩阵存成了双向赋值有一个经典坑必须让graph[i][j]和graph[j][i]同时更新为同一个较小值否则单向更新会导致对称性错误跑出来的树权值可能偏大。5.3 模板变量的语义一定不能记混今天写Prim时有个地方卡了很久我一直把lowcost误当成当前节点到起始点的距离于是每轮更新时都在比较dist[u]graph[u][v]和上一个节点的距离叠加完全偏离了最小生成树的语义。后来我在代码注释里反复强调lowcost[v]表示v到已选集合的最短边权并每次更新时只取graph[u][v]和lowcost[v]的较小值不叠加历史路径。这个混淆的根源在于前两周刷Dijkstra太熟了肌肉记忆让我看到更新距离就自动写dist[v] min(dist[v], dist[u] w)。Prim里根本没有w这一步。写代码时先停顿一下问自己我现在维护的到底是什么如果是到集合的距离就不应该加路径和如果是到源点的距离才需要加路径和。这是今天最大的心得之一。5.4 一个打通两个模板的对照方法我把两个算法写成了一组对照Prim里的已选集合对应Kruskal里的并查集连通块。Prim每次扩张集合时选的是跨集合边界的最小边这等价于在Kruskal处理边列表时的尝试加入边并检查是否会形成环的过程。进一步说两个算法本质都是在维护森林到树的合并过程只是Prim一次只主动合并一个点而Kruskal每次从全局边里选一条来合并两个连通块。用这个视角看它们都是贪心套路的具体实例。有个实用的小技巧当我们手头有现成的Dijkstra模板时改成Prim只需三处改动去掉dist数组更新中的路径叠加把更新条件从dist[v] dist[u] w改为lowcost[v] w最后把源点距离改为lowcost[source]0。今天我按照这个思路在十五分钟内改写并跑通了Prim再配合并查集模板独立写完Kruskal感觉两个算法在脑子里稳稳扎根了。6. 最小生成树的现实应用训练营之外的算法价值6.1 从网络布线到集群设计最小生成树在现实中的身影比我之前想象的要密集得多。最直观的是铺设网络线路或电力线路有一批站点需要连通站点之间建设线路的成本各不相同如何用最低总成本让所有站点连通这就是最小生成树的原生场景。5G基站选址、光纤铺设、城市管网规划核心都离不开最小生成树。在数据中心里设计树形网络拓扑时也常会用到最小生成树。虽然不是所有场景都直接生成最终拓扑但最小生成树可以作为初始基线先得到一个低成本的连通方案再在这个基础上增加冗余边或调整线路。6.2 聚类分析与图分割最小生成树还能用于聚类。把数据点看作节点点与点之间的距离作为边权先构建最小生成树然后根据某个阈值切断若干条最长的边树就会分裂成若干棵子树每棵子树代表一个簇。这个思路在某些场景下比K-Means更稳定因为不需要预设聚类中心的坐标而且能够处理非凸形状的簇。我在学习谱聚类时见过类似思想当时没有意识到最小生成树的连接关系也能做这种分割。6.3 为什么次小生成树也能成为进阶题今天训练营的打卡内容里还有一道进阶题让我思考了次小生成树如果某条最小生成树上的边坏了能不能快速找到仅次于最优方案的第二套方案更常见的问法是在最小生成树上加一条非树边之后形成的环里去掉一条最大边从而得到一棵新的树。这个思路建立在Kruskal或Prim生成的树之上先求最小生成树然后枚举每一条不在树上的边尝试替换树上的最大边得到新的权重和取最小即可得到次小生成树。这个变化让我意识到今天学的是地基后续的扩展题目都可能围绕树边替换环上最大边这些概念展开。如果对Kruskal中并查集合并的过程理解不透彻后面做次小生成树时很容易绕晕。6.4 关于生成树权值唯一性的冷知识最后记录一个今天被触动到的细节一棵图可能有多棵不同的生成树但所有最小生成树的权值和一定相同。换句话说边权重不同的情况下生成树形态可能不同但总和别想变。这个性质在证明和构造题目中都很好用。遇到判断某条边是否一定出现在最小生成树中这种问题不能只凭直觉说它权值小就一定入选需要借助Kruskal排序和并查集来判断如果排序过程中排在它之前的边都无法把它的两个端点连通那么它必然出现在某棵最小生成树中但不是唯一的。这种边可以称为必要边。如果两个端点已经被更小的边连通那它一定不会出现在任何最小生成树中可以称为无用边。今天把Prim和Kruskal完整推完之后我最大的体会是它们就像两把形状不同的钥匙捅的是同一把锁。Prim从点出发适合稠密图的直觉Kruskal从边出发天生和边列表、并查集配合默契。无论用哪个判断全局正确性的关键都落在贪心选择会不会把未来的最优解排除在外上。这个思考方式和图论里很多其他问题的思路是一脉相承的。如果读者也在刷最小生成树我建议不要去背代码而是把今天讲的循环不变量理解透Prim的低cost数组永远维护着每个外部节点到已选集合的最小边权Kruskal的并查集永远维护着当前候选边构成的森林连通性。理解透这两句话再去看任何题解都会觉得清楚很多。代码细节可以随时查底层直觉一旦建立后面做次小生成树、最短路径树、网络流建模都会更顺手。 
长河君 · 2026/10/13 21:19:13 · 阅读 1.2k 最小生成树算法精讲：Prim与Kruskal的原理、对比与选型
1. 从最短路径到最小生成树第57天的学习坐标今天已经是训练营第五十七天。前两周我们一直在围着图论转一口气刷完了深度优先遍历、广度优先遍历、拓扑排序、最短路径系列好不容易觉得自己和图熟了结果今天的两节课直接把我拉回原来我对图的理解还很浅的状态。今天的内容是往最小生成树方向走的精讲部分的重点是Prim算法和Kruskal算法。坦白说刚看到课表的时候我有点困惑。最短路径解决的是从A点到B点怎么走最近最小生成树解决的问题却是怎么用最少的边让整张图连通两个问题听起来接近实际目标完全不同。我一开始甚至觉得最小生成树没什么用直到跟着精讲里案例一步步推完才意识到它在网络规划、集群设计、电路布线这类场景里有多常见。这篇文章不是我抄讲义整理的笔记而是我把今天课程里的两个算法揉碎、重新用自己方式表达出来的学习复盘。适合两类读者一类是和我一样正在按训练营节奏刷图论的初学者另一类是已经知道这两个算法名字、但始终没搞懂为什么得这么写的读者。我会直接讲原理、给模板、写复杂度也会把今天我踩过的坑和想通的关键点都放进去。先立住一个基本认知什么叫生成树一个连通的无向图如果挑出一部分边让所有节点依然连通并且不形成任何环那这部分边和全部节点一起就构成一棵树。因为边数等于节点数减一所以这棵树能覆盖所有顶点。在满足这个条件的所有树里边的权重和最小的那棵就是最小生成树。接下来所有讨论都是围绕找到这棵树展开的。2. Prim算法精讲把已经连好的部分当作一个大节点2.1 从一个起点开始像滚雪球一样扩张Prim算法的核心思想我记得课程里的说法是从一个顶点出发逐步扩大生成树的顶点集合。我自己的理解更直白把已经纳入最小生成树的那些节点想象成一个超级大节点每次从这个超级节点和外面的节点之间挑一条最短的边把边另一边的新节点吞进来重复直到所有节点都在超级节点里。这个过程是不是听起来很眼熟如果你刷过Dijkstra会发现Prim在每一步选一个最小的东西这个节奏上和Dijkstra有点像。但两者的更新逻辑有本质区别Dijkstra维护的是某个起点到各个节点的最短距离Prim维护的是整个已选节点集合到各个未选节点的最小连接代价。也就是说Dijkstra里每个节点只有一个起点维度的距离Prim里每个节点的距离会随着集合扩张而动态变成离集合里任意节点最近的那条边的权值。我用一个很简单的例子来推演。假设有4个节点1号节点和2号节点之间权值为12号和3号之间权值为33号和4号之间权值为41号和4号之间权值为52号和4号之间权值为2。从1号开始已选集合是{1}这时1到2的权值是11到4的权值是5选最小的边是1-2把2加进来。现在已选集合是{1,2}对3号来说从它到已选集合最近的边是2-3权值3对4号来说从它到已选集合最近的边是2-4权值2比原先的1-4权值5更小所以更新。于是现在找最小的未选节点连接代价2号到4号是21号到4号是5所以选4号进来最后剩下3号最近的边是3-4权值4。整棵树的边就是1-2、2-4、3-4总代价7。我把这个例子在手写纸上画了三遍才彻底明白更新的是到集合的距离这句话。2.2 为什么贪心在这里不会失效今天最大的一个思想障碍就是每一步都贪心地选最小边真的能保证最后全局最小课程里给了一个非常扎实的论证我想用自己的话复述一遍。假设当前已选集合叫S剩余节点叫T。我们要找一条跨越S和T的边。如果当前选的是从S到T权值最小的一条边e那么在所有可能的最终最小生成树里至少有一棵树是包含e的。原因可以用切断边互换来证明假如有一棵最小生成树不包含e那它一定有一条别的跨过S和T的边f。把e加进这棵树会形成一个环环里必然包含f如果把f去掉、把e放回去整棵树依然连通且边数不变但总权值不会变大因为e的权值小于等于f。所以保留e不会丢掉全局最优解。这个证明我一开始绕了很久关键在于至少有一棵最优解包含这条边而不是每一步都必须包含这条边。贪心算法不需要保证每一步都走在唯一的最优路线上只要保证当前选择能被某个全局最优解兼容然后一路走下去最后得到的局部选择集合就是完整的全局最优解。Prim的每一步选的都不是最短的一条边而是跨边界的最短边这个边界会不断外扩所以证明了每个局部决策都有存在最优解的兼容性。想通这一点再看代码理解会猛然深一层。2.3 朴素Prim的完整模板和复杂度拆解下面这个模板是我今天按照课程思路整理出来的使用邻接矩阵存图适合节点数比较少、图比较稠密的场景。我用Python写出来细节处都加了注释import sys def prim(n, graph): # graph[i][j] 表示 i 到 j 的边权不连通设为 INF INF 10 ** 9 visited [False] * n # lowcost[j] 表示 j 到当前已选集合的最小边权 lowcost [INF] * n lowcost[0] 0 total 0 parent [-1] * n # 记录边从哪里来方便还原树结构 for _ in range(n): # 找出当前未选节点中 lowcost 最小的节点 u -1 min_cost INF for j in range(n): if not visited[j] and lowcost[j] min_cost: min_cost lowcost[j] u j if u -1: return None # 图不连通不存在生成树 visited[u] True total min_cost # 用新加入的节点 u 去更新其他未选节点的 lowcost for v in range(n): if not visited[v] and graph[u][v] lowcost[v]: lowcost[v] graph[u][v] parent[v] u return total, parent if __name__ __main__: n 4 graph [[0, 1, 10**9, 5], [1, 0, 3, 2], [10**9, 3, 0, 4], [5, 2, 4, 0]] res, parent prim(n, graph) print(res) # 输出 7复杂度方面外层循环执行n次每次找最小lowcost的过程需要遍历n个节点内层更新也要遍历n个节点所以朴素版的时间复杂度是O(n²)。空间上lowcost数组和visited数组各占O(n)邻接矩阵占O(n²)。对于稠密图O(n²)是很划算的但如果图是稀疏的尤其边数接近顶点的量级时这个复杂度就显得吃力了。2.4 为什么训练营先讲Prim而不是Kruskal我猜测课程顺序安排是有用意的。Prim更适合在邻接矩阵上讲解因为它的核心动作是找集合边界上的最小边而邻接矩阵天然支持快速访问任意一条边。同时Prim和Dijkstra的代码结构高度相似先讲Prim可以巩固前几天的Dijkstra理解让从一个点出发逐步扩展的思路在最短路径和最小生成树两个问题上形成对照。今天边听课边把两个模板并排看确实能发现许多共通的骨架都是维护一个visited数组都有一个不断更新的代价数组都有一个每轮取最小值的循环。只是更新语义不同一个关注到源点的最短距离一个关注到已选集合的最小边权。3. Kruskal算法精讲排序之后的并查集舞台3.1 把所有边拉出来排队从最小的开始挑如果说Prim是从点往外长Kruskal就是从边直接挑。Kruskal的思路非常朴素把图中所有边按权值从小到大排序然后依次考察每条边如果这条边连接的两个顶点目前还不在一棵子树里就把它选进生成树如果已经在同一棵树里说明加入这条边会形成环直接跳过。重复直到选满n-1条边。这个是否在同一棵树里的判断就是并查集的经典应用场景。并查集支持两种操作查找某个节点属于哪个集合合并两个集合。在Kruskal里我们利用并查集维护当前哪些点已经连通成块。判断一条边的两个端点是否在同一个集合只需要两次find如果不在union一下把两个集合合并。3.2 为什么Kruskal的贪心也是对的Kruskal的贪心正确性可以用一个和Prim类似但切入点不同的环性质来理解。最小生成树有一个著名的性质对于图中的任意一个环环上权值最大的边一定不属于任何一棵最小生成树只要有更小的替代边存在它就不可能出现在最优解里。Kruskal每次从小到大取边如果某条边会形成环说明在当前已经选出的若干条边中已经有一条路径连接了这条边的两端。由于我们是按权值从小到大处理的这条路径上的每条边的权值都小于等于当前边所以当前边就是这个环上最大的边应当被舍弃。这个证明我花了一点时间才转过弯关键在于理解环上最大的边会被淘汰这个性质。Kruskal用排序保证了每次遇到环时当前边一定是环上最晚出现的、至少不小于环上其他边的边所以淘汰它是安全的。这个思路和Prim的切断互换完全不同但都保证了全局最优。3.3 并查集模板与Kruskal完整实现今天写的Kruskal模板里我额外把并查集的路径压缩和按秩合并都加上了因为这两项优化能让并查集的操作近乎常数级别从而让整个算法的时间复杂度主要由排序决定。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.sort(keylambda x: x[2]) # 每条边表示为(u, v, w) dsu DSU(n) total 0 cnt 0 tree_edges [] for u, v, w in edges: if dsu.union(u, v): total w cnt 1 tree_edges.append((u, v, w)) if cnt n - 1: break if cnt ! n - 1: return None # 无法生成树图不连通 return total, tree_edges时间复杂度上排序是O(mlog m)m为边数。并查集操作在路径压缩和按秩合并下近似O(1)所以整体复杂度可以按排序复杂度来估算。空间复杂度主要是存储边列表的O(m)以及并查集的O(n)。3.4 今天在并查集细节上踩的一个坑课上练习时我在union的写法上踩了个坑。一开始我的union只是简单地把一个根的parent指向另一个根没有处理rank也没有比较两棵子树的高度。测试小图没问题数据一到几千个节点、边几乎每个案例都慢了不少。后来我把路径压缩和按秩合并补上速度才恢复正常。原因其实很简单如果union随意连并查集的树可能退化成链find操作会一路追到很长导致整体复杂度退化。这个问题在Kruskal里尤其明显因为算法全程都在反复调用find并查集的效率直接影响整体成绩。还有一个更隐蔽的坑我在实现find时一开始用的是递归在超过十万条边的案例里直接爆了Python默认递归深度。换成迭代写法之后问题就消失了。如果读者也喜欢用递归写find最好注意设置sys.setrecursionlimit但说实话迭代版更稳既然能顺手写迭代就别给递归留风险。4. 两种算法的选型对比稠密图与稀疏图的取舍逻辑4.1 一张表看清差异今天训练营把两个算法放在一起讲我觉得最有用的环节就是对比它们适用场景。我用一张表整理了核心差异方便读者直接抓住选型的判断依据对比维度Prim算法朴素版Kruskal算法图存储方式适合邻接矩阵适合边列表时间复杂度O(n²)O(mlog m)适用图类型稠密图m接近n²稀疏图m接近n核心数据结构visited数组、lowcost数组并查集贪心角度从顶点集合扩张出发从边权排序出发是否依赖排序否是处理非连通图会在循环中找不到可选节点会因边数不足n-1而返回None这里的n是顶点数m是边数。稠密图里m约等于n²那么Kruskal的复杂度为O(n²log n)而Prim朴素版是O(n²)常数更小稀疏图里m约等于nKruskal的复杂度为O(nlog n)而Prim仍然要O(n²)所以Kruskal优势明显。4.2 我选型时的思考顺序今天在做课后题时我总结了一套自己的判断顺序先看顶点数和边数哪个量级更高。如果顶点数量很少比如n只有几十那么怎么选都无所谓直接用自己最熟的模板就行。如果n很大再看边数m当m小于nlog n的量级时优先Kruskal因为排序成本低并查集接近线性当m接近n²时邻接矩阵版的Prim反而更容易写出低复杂度的实现。另一个判断角度是看输入数据格式。很多实际问题里数据给的是边列表那么写Kruskal几乎不需要额外转换直接排序即可如果数据给的是邻接矩阵或者边权矩阵天然存在Prim更顺手。这个选择会受到输入格式的强烈影响考试或者刷题时可以把这个当成重要依据。4.3 堆优化Prim的提升空间课程里提到朴素Prim适合稠密图但到了稀疏图除了Kruskal之外Prim也可以用堆优化来拯救。堆优化Prim的思路是把每次找最小lowcost这件事交给优先队列。每次从堆里弹出当前离集合最近的点然后用它去更新周围节点把更小的候选权值再次入堆。这样时间复杂度可以从O(n²)优化到O(mlog n)因为每条边最多被用来更新一次。我整理了一个堆优化Prim的简易版本供读者参考import heapq def prim_heap(n, graph): # graph 为邻接表: graph[i] [(j, w), ...] visited [False] * n heap [(0, 0)] # (cost, node)从节点0开始 total 0 cnt 0 while heap and cnt n: cost, u heapq.heappop(heap) if visited[u]: continue visited[u] True total cost cnt 1 for v, w in graph[u]: if not visited[v]: heapq.heappush(heap, (w, v)) if cnt ! n: return None return total这里有个容易误解的点堆里的元素即使后来被发现不是最优也不会被主动删掉只能靠visited来跳过所以堆的大小可能比n大不少。但实际运行中堆中的很多过期条目会被快速跳过总体效率依然可观。堆优化Prim在边稀疏、但依然想用Prim思路时很有效。4.4 选型时要考虑的隐藏因素除了复杂度今天让我意外的是选型还会受到边权相同时的稳定性影响。Kruskal在边权相等时选择的边的具体集合取决于排序后的稳定顺序但是最小生成树的权重和不会变Prim在边权相同时选哪个邻居也不会影响总权重。无论选哪棵总权重是一样的所以从做题角度不用担心输出边的顺序。但如果是实际工程有时会希望生成树的形态尽量平衡这时可以考虑在排序里加入按节点编号的次级排序或者让Prim的遍历顺序有确定性。还有一个容易被忽视的因素如果输入图本身就是非连通的两个算法的表现不同。Prim循环结束时会发现还剩节点没访问应该返回不存在Kruskal结束时会发现边数不够n-1也应该返回不存在。今天刷题时有道题我忘了判断非连通直接按默认值打印结果答案错误。这是最小生成树问题里最常见的低级失误值得单独提醒。5. 模板之外的细节环判断、无穷大与输入边界5.1 邻接矩阵里INF的设定要谨慎Prim的邻接矩阵会遇到一个实际问题不存在的边权用什么表示如果用一个特别大的数比如10⁹那么要注意相加时不会溢出或者在更新lowcost时要明确判断。我一开始犯过错误把不连通边的权值设为0结果Prim会把不存在的边当成权值0的边选进去。正确的做法是设成一个大数并确保大数大于所有真实边权之和这样才能保证不会选它。如果顶点数很多、边权也可能很大建议用类似10**18的值。非连通图场景更要注意如果某个节点和其他节点完全没有边lowcost[i]会一直是INF选点时min_cost也是INF此时u会等于-1要立刻返回不存在生成树。这个判断在训练营的例题中经常被隐藏很多同学因为没有及时判断而超时或者报错。5.2 Kruskal里的并查集需要注意自环和重边自环就是i到i的边。在Kruskal里自环的union一定返回False因为find(i)和find(i)本身相同所以会被直接跳过逻辑上没问题。但重边要注意如果两条边连接同一对节点但权值不同排序后只会先选小的后面那条遇到时会发现两个点已经连通直接跳过。所以Kruskal天然能正确处理重边不需要预处理去重。在Prim里如果邻接矩阵存的是最小边的权值那重边也不会有问题因为prim只关注最小值。但是如果邻接矩阵存成了双向赋值有一个经典坑必须让graph[i][j]和graph[j][i]同时更新为同一个较小值否则单向更新会导致对称性错误跑出来的树权值可能偏大。5.3 模板变量的语义一定不能记混今天写Prim时有个地方卡了很久我一直把lowcost误当成当前节点到起始点的距离于是每轮更新时都在比较dist[u]graph[u][v]和上一个节点的距离叠加完全偏离了最小生成树的语义。后来我在代码注释里反复强调lowcost[v]表示v到已选集合的最短边权并每次更新时只取graph[u][v]和lowcost[v]的较小值不叠加历史路径。这个混淆的根源在于前两周刷Dijkstra太熟了肌肉记忆让我看到更新距离就自动写dist[v] min(dist[v], dist[u] w)。Prim里根本没有w这一步。写代码时先停顿一下问自己我现在维护的到底是什么如果是到集合的距离就不应该加路径和如果是到源点的距离才需要加路径和。这是今天最大的心得之一。5.4 一个打通两个模板的对照方法我把两个算法写成了一组对照Prim里的已选集合对应Kruskal里的并查集连通块。Prim每次扩张集合时选的是跨集合边界的最小边这等价于在Kruskal处理边列表时的尝试加入边并检查是否会形成环的过程。进一步说两个算法本质都是在维护森林到树的合并过程只是Prim一次只主动合并一个点而Kruskal每次从全局边里选一条来合并两个连通块。用这个视角看它们都是贪心套路的具体实例。有个实用的小技巧当我们手头有现成的Dijkstra模板时改成Prim只需三处改动去掉dist数组更新中的路径叠加把更新条件从dist[v] dist[u] w改为lowcost[v] w最后把源点距离改为lowcost[source]0。今天我按照这个思路在十五分钟内改写并跑通了Prim再配合并查集模板独立写完Kruskal感觉两个算法在脑子里稳稳扎根了。6. 最小生成树的现实应用训练营之外的算法价值6.1 从网络布线到集群设计最小生成树在现实中的身影比我之前想象的要密集得多。最直观的是铺设网络线路或电力线路有一批站点需要连通站点之间建设线路的成本各不相同如何用最低总成本让所有站点连通这就是最小生成树的原生场景。5G基站选址、光纤铺设、城市管网规划核心都离不开最小生成树。在数据中心里设计树形网络拓扑时也常会用到最小生成树。虽然不是所有场景都直接生成最终拓扑但最小生成树可以作为初始基线先得到一个低成本的连通方案再在这个基础上增加冗余边或调整线路。6.2 聚类分析与图分割最小生成树还能用于聚类。把数据点看作节点点与点之间的距离作为边权先构建最小生成树然后根据某个阈值切断若干条最长的边树就会分裂成若干棵子树每棵子树代表一个簇。这个思路在某些场景下比K-Means更稳定因为不需要预设聚类中心的坐标而且能够处理非凸形状的簇。我在学习谱聚类时见过类似思想当时没有意识到最小生成树的连接关系也能做这种分割。6.3 为什么次小生成树也能成为进阶题今天训练营的打卡内容里还有一道进阶题让我思考了次小生成树如果某条最小生成树上的边坏了能不能快速找到仅次于最优方案的第二套方案更常见的问法是在最小生成树上加一条非树边之后形成的环里去掉一条最大边从而得到一棵新的树。这个思路建立在Kruskal或Prim生成的树之上先求最小生成树然后枚举每一条不在树上的边尝试替换树上的最大边得到新的权重和取最小即可得到次小生成树。这个变化让我意识到今天学的是地基后续的扩展题目都可能围绕树边替换环上最大边这些概念展开。如果对Kruskal中并查集合并的过程理解不透彻后面做次小生成树时很容易绕晕。6.4 关于生成树权值唯一性的冷知识最后记录一个今天被触动到的细节一棵图可能有多棵不同的生成树但所有最小生成树的权值和一定相同。换句话说边权重不同的情况下生成树形态可能不同但总和别想变。这个性质在证明和构造题目中都很好用。遇到判断某条边是否一定出现在最小生成树中这种问题不能只凭直觉说它权值小就一定入选需要借助Kruskal排序和并查集来判断如果排序过程中排在它之前的边都无法把它的两个端点连通那么它必然出现在某棵最小生成树中但不是唯一的。这种边可以称为必要边。如果两个端点已经被更小的边连通那它一定不会出现在任何最小生成树中可以称为无用边。今天把Prim和Kruskal完整推完之后我最大的体会是它们就像两把形状不同的钥匙捅的是同一把锁。Prim从点出发适合稠密图的直觉Kruskal从边出发天生和边列表、并查集配合默契。无论用哪个判断全局正确性的关键都落在贪心选择会不会把未来的最优解排除在外上。这个思考方式和图论里很多其他问题的思路是一脉相承的。如果读者也在刷最小生成树我建议不要去背代码而是把今天讲的循环不变量理解透Prim的低cost数组永远维护着每个外部节点到已选集合的最小边权Kruskal的并查集永远维护着当前候选边构成的森林连通性。理解透这两句话再去看任何题解都会觉得清楚很多。代码细节可以随时查底层直觉一旦建立后面做次小生成树、最短路径树、网络流建模都会更顺手。