Kruskal 算法

定义

Kruskal 算法是求解无向连通图最小生成树(MST)的经典贪心算法,由 Joseph Kruskal 于 1956 年提出。

原理

将所有边按权值从小到大排序,依次考察每条边:若这条边连接的两个顶点尚不在同一连通分量中,则将其加入生成树,否则跳过。使用并查集(Union-Find)高效判断连通性,直至选出 V-1 条边。时间复杂度为 O(E log E),主要来自排序。

应用

用于通信网络、电网、管道等基础设施的最小成本连接设计,也是聚类分析中单链接聚类的理论基础。

与 Prim 算法对比

Kruskal 以边为主导,依赖排序和并查集,适合边数较少的稀疏图;Prim 以点为主导,配合优先队列在稠密图上更有优势。两者正确性均由最小生成树的切分性质保证。