最小生成树：割性质、Kruskal/Prim/Borůvka 与线性时间开放问题
内容提要
本文系统讲解最小生成树，严格证明割性质、环性质与唯一性条件，梳理从Borůvka、Kruskal、Prim到线性时间算法的百年谱系，并用可复现实验比较三种经典算法。实测表明“稀疏用Kruskal、稠密用Prim”只对一半，缓存与数据规模常比边密度更关键；Borůvka遇并列边须用统一次序打破，否则会成环。
延伸解读
并列边权下的正确性细节
文章强调割性质有一般版和严格版之分：一般版允许并列，保证存在某棵MST包含所选边；严格版要求唯一最轻边，才保证所有MST都包含。Borůvka算法若只按权重选边，并列时不同分量可能选到成环的边，必须用统一次序（如(w,id)）打破并列，才能保证正确性。
实验揭示的选型反例
实测表明“稀疏用Kruskal、稠密用Prim”只对一半：n=4096时Prim在平均度数16以上就快于Kruskal，完全图上快8倍；但n=2^20时Kruskal和Borůvka反而快1.3到3倍。原因是缓存与随机访存：小图数据在缓存内，Prim的堆操作少；大图Prim的堆和键值数组随机访存，而Kruskal和Borůvka顺序访存。
工程实现中的常见陷阱
文章列出多个陷阱：比较函数写成差值可能溢出；浮点NaN破坏严格弱序；Borůvka并列边成环；懒堆Prim最坏情况堆涨到m项；递归find在按秩合并下深度安全，但只路径压缩不按秩合并可能爆栈。并查集不是Kruskal瓶颈，优化应从排序入手。
理论开放问题与工程取舍
比较模型下确定性线性时间MST算法是否存在仍是开放问题：随机化有期望O(m)算法，整数权重字长RAM有确定性线性算法，但仅比较边权时最好上界是O(m α(m,n))。理论最优算法常数大、复杂，工程中Filter-Kruskal等实用算法更受青睐，其期望时间与二叉堆Prim相同。
Q&A
最小生成树的割性质在边权有并列时还成立吗？
成立，但需要区分两个版本。一般版：设割尊重已选边集A，e是跨割边中权重最小的边之一，则A∪{e}包含于某棵MST。严格版：若e是跨割边中唯一的最轻边，则e属于每一棵MST。一般版是Kruskal和Prim在边权并列时正确性的基础。
为什么Borůvka算法在边权有并列时可能产生环？如何避免？
Borůvka每轮让每个分量选最轻出边，若只比较权重，不同分量可能对并列边做出不一致的选择，导致选出的边形成环。避免方法是使用统一的严格全序，例如按(w, id)比较，这样所有分量对并列边的偏好一致，不会成环。
Kruskal和Prim算法分别适合什么场景？
传统经验是稀疏图用Kruskal、稠密图用Prim，但实测表明这取决于数据规模和缓存。n=4096时Prim在中高密度下更快；n=2^20时Kruskal和Borůvka比Prim快1.3到3倍。选型应综合考虑比较次数、访存模式和并行度。
最小生成树是否唯一？什么条件下唯一？
若所有边权互不相同，则MST唯一。逆命题不成立：边权有并列时MST也可能唯一。工程上可通过给边权加次级键（如边编号）构造严格全序，使MST唯一，且该MST也是原权重下的MST。
比较模型下是否存在确定性线性时间的最小生成树算法？
这是著名的开放问题。目前已知：随机化算法可期望线性时间（KKT 1995）；整数权重在字长RAM下可线性时间（Fredman-Willard 1994）；确定性比较算法最好上界是O(m α(m,n))（Chazelle 2000）。Pettie-Ramachandran算法可证最优，但运行时间T*(m,n)量级未知。
MST与单链接聚类有什么关系？
单链接层次聚类与MST等价：删掉MST中最重的k-1条边，剩下的k个连通分量就是单链接聚类在k类时的结果。Kruskal的合并顺序对应聚类树的合并顺序。
实现MST算法时有哪些常见陷阱？
常见陷阱包括：图不连通时Prim只覆盖一个分量；比较函数写成差值可能导致溢出；浮点权重含NaN破坏严格弱序；Borůvka遇并列边可能成环；懒堆Prim内存可能涨到m项；递归find在只做路径压缩时可能爆栈。
