本文系统讲解最小生成树，严格证明割性质、环性质与唯一性条件，梳理从Borůvka、Kruskal、Prim到线性时间算法的百年谱系，并用可复现实验比较三种经典算法。实测表明“稀疏用Kruskal、稠密用Prim”只对一半，缓存与数据规模常比边密度更关键；Borůvka遇并列边须用统一次序打破，否则会成环。

今天学习了最小生成树算法，包括Prim、Kruskal和Borůvka。Prim适合密集图，Kruskal适合稀疏图，Borůvka适合大规模图的并行处理。现代算法常结合使用，先用Borůvka减少边数，再用Prim或Kruskal完成。