KruskalKruskal's algorithm
按边权从小到大处理边，仅接受连接两个不同分量的边。
- 核心约束
- 已选边构成森林；并查集判定一条边是否会形成环，割性质保证安全边可以扩展为最小生成树。
- 适用问题
- 边列表形式的无向加权图，或需要按边权逐步合并分量的问题。
- 边界与取舍
- 允许负边权和相同权值；非连通图得到最小生成森林。全局排序可能成为主要成本，最小生成树也不保证任意两点间的最短路。
时间与空间#
V 为顶点数，E 为无向边数；按边权排序，使用路径压缩与按秩合并。
- 时间复杂度
- 辅助空间
- ，包括排序所需的边副本
从小到大选不形成环的边。图不连通时得到最小生成森林；允许负边和相同权重。若边已按权重有序，可省排序阶段。
基础原理参考资料
Princeton · KruskalMST排序、并查集和最小生成森林的实现。