22篇的带权区间调度不能总选最早结束的区间。Kruskal却可以反复选当前最轻、且不形成环的边，最终得到最小生成森林。区别不在于两个规则哪一个“更自然”，而在于是否能证明局部选择仍属于某个全局最优解。

本篇先给出割与交换证明，再把无环边集合抽象成图拟阵。教学实现复用10篇并查集，检查的是无环约束；优化目标的正确性需要另外证明。

无向多重图的目标

输入n个顶点，编号0到n−1，以及m条无向边(u,v,weight)。权重为整数，允许负权、相等权、平行边和自环；每个输入位置是独立边ID。输出总权重与选中的边ID。

若原图连通，目标是最小权生成树。若有c个连通分量，目标是在每个原分量内选生成树，合计n−c条边；孤立点也算分量。空图返回总权重0和空边集。

这不是在任意子图中最小化权重。允许任意森林时可以不连接某些顶点；允许任意连接子图且存在负权环时，加入额外边反而可能降低总权重。生成森林同时要求连接原分量与无环，两个条件都不能省略。

Kruskal只负责维持森林

将边按(weight,id)递增排序，开始时选边集A为空。扫描到边(u,v)时，用并查集判断两端是否已经连通：不连通就选入并合并，已连通则跳过。

加入连接两个分量的边不成环；跳过同分量边不改变已有连接。扫描结束后，原图任意边的两端都处于同一选中分量，所以选中森林与原图具有相同连通分量划分。由此可知它有n−c条边。

自环的两端始终连通，自然跳过；平行边仍按各自ID处理。负权不改变环的判断，相等权用ID固定先后，但不承诺最小生成森林唯一。

安全选择需要一个可延续的不变量

保持不变量：存在某个最优生成森林F包含当前A。初始A为空显然成立。现在要选最轻可加入边e=(u,v)，取当前A中包含u的分量作为割的一侧。

这个割尊重A，即A没有边跨割。e是最轻跨割边之一：若有更轻跨割边，它应更早被扫描；它的两端在当时也不可能已被A连接，否则之后仍连通，不会分处当前割两侧。因此那条边早已被接受，与当前割的定义矛盾。

若e已经在F里，不变量保持。否则e两端属于同一个原图分量，F中有连接两端的唯一路径；路径上至少一条边f跨过该割。f不在A中，并且w(e)≤w(f)。

用e替换f，仍然是生成森林且仍包含A，新权重不大于F。由于F已最优，新森林也最优，并包含A∪{e}。这个交换步骤完成归纳，扫描结束时A本身就是最优生成森林。

相等权时，正确表述是“存在一个包含这条选择的最优解”，不是“所有最优解都包含这条边”。三角形三条边同权时，任意两条都是生成树，没有哪一条必须出现在所有解里。

图拟阵把交换条件提炼出来

一个拟阵由有限底集E和独立集族I组成，需要空集独立、遗传性和增广性。遗传性表示独立集的子集仍独立；增广性表示若A、B独立且|A|<|B|，则B中存在一个不在A里的元素，可加入A而仍独立。

把图的边作为底集，无环边集作为独立集，空集和遗传性直接成立。增广性可按分量证明：森林A有n−|A|个分量。若B没有边跨越A的不同分量，那么B在每个A分量内部最多放“该分量顶点数减一”条边，合计至多|A|，与|B|>|A|矛盾。故B有一条跨分量边可加入A。

图拟阵的极大独立集就是每个原分量的生成树，所有这种基都有n−c条边。拟阵贪心定理因此能解释Kruskal：按递增权重扩充到一个基，得到最小权基。对任意符号的权重，都须保留“基”或固定基数条件，不能偷换成任意独立集的最小权问题。

这一抽象不是替代前面的割证明，而是指出哪些新问题也可能支持交换式贪心。如果可行集没有增广性质，仅有“删去元素仍可行”还不够。

背包给出遗传但不能增广的例子

容量为4，有一件大小3的物品a，以及两件大小2的物品b、c。集合{a}和{b,c}都可行，且前者元素更少；但把b或c加入{a}都会超出容量。增广性质失败，所以不能直接应用拟阵贪心定理。

若价值分别为5、3、3，按价值最高者先选会得到{a}，价值5；最优却是{b,c}，价值6。这同时提供集合结构反例与具体目标失败例，而不只是说“贪心有时不行”。按单位价值排序也需要独立证明，不能从一种排序规则失败就推出另一种一定成功。

成本与并查集的边界

初始化并查集O(n)，排序O(m log(m+1))。扫描调用O(m)次并查集操作，按10篇按秩合并与路径压缩的总界，计O(m α(n))摊还成本，n很小时用常数基例。因此总成本写为O(n+m log(m+1)+m α(n))，额外空间O(n+m)。

排序界是确定性最坏界，并查集项是操作序列的摊还界，均不是随机输入平均或高概率结论。允许任意多平行边时，不能借简单图的m≤n²把log m无条件改成log n。Python权重比较和大整数求和另有位长成本。

并查集只回答连通性，不提供树上最大边、路径或交换证书；本篇返回所选边后，用独立参照验证它的可行性与小图最优值。未来若要高效核验大图最优性，还需要定义额外证书或查询结构。

可复跑检查

实现位于examples/advanced-algorithms/kruskal.py，minimum_spanning_forest(n,edges)返回总权重及按选择顺序排列的边ID。负n抛ValueError，非法端点抛IndexError，即使非法边是自环也先拒绝。仓库根目录运行：

1
python3 examples/advanced-algorithms/check_kruskal.py

独立参照枚举边子集，用邻接表DFS检查它与原图具有相同分量，并且边数等于n−c。在每个分量内，连通至少需要顶点数减一条边；总数恰好达到这个下限便保证无环，所以此检查也排除了自环与平行边形成的冗余。参照不调用并查集。

本次实际执行覆盖64个三顶点图、343个子集，7个边界图、25个子集；种子20260920的200个随机图再核对12337个子集，另有5个拒绝检查和1个稳定平局结果。真实stdout保存在examples/advanced-algorithms/results/kruskal.json。

这是有限小图最优性与输出可行性检查，不是对所有图的证明，也没有测量大型图吞吐。一般正确性由安全割与交换不变量保证，代码检查用于发现实现偏差。

练习

  1. 构造带平行边和相等权的三顶点图，按边ID执行Kruskal。找出两个不同的最优边集，解释为什么割证明没有声称最优解唯一。
  2. 对容量4的三个物品反例，分别验证遗传性和增广性。若改成每件物品大小均为1且最多选两件，增广证明会怎样变化？

参考资料