Kruskal's Algorithm

定义

Kruskal 算法（克鲁斯卡尔算法）是求解连通无向图最小生成树（MST）的贪心算法。

算法思想

1. 将所有边按权值从小到大排序
2. 依次选取权值最小的边
3. 若该边连接的两个顶点不在同一连通分量中（不形成环），则加入 MST
4. 重复步骤 2-3，直到选了 $V-1$ 条边

关键数据结构

并查集（Union-Find）：用于高效判断两个顶点是否在同一连通分量中。

时间复杂度

• 排序边：$O(E\log E)$
• 并查集操作：近似 $O(1)$
• 总复杂度：$O(E\log E)$

适用场景

稀疏图（边数远小于 $V^2$）的最小生成树问题。