Kruskal算法 vs Prim算法

两种经典MST贪心算法分别从边和顶点视角出发，通过不同的数据结构和贪心策略构建最小生成树

共同点

都基于贪心策略，属于GENERIC-MST框架的具体实现
正确性都依赖安全边定理（定理21.1）：每次选取的边都是安全边
都要求输入为连通无向图
使用二叉堆时时间复杂度相同，均为 $O (E l g V)$
都能正确处理含负权边的图（MST问题本身不限制边权正负）

关键区别

维度	Kruskal算法	Prim算法
核心视角	全局——按边权排序，逐条考虑所有边	局部——从一个起始顶点向外扩展
贪心策略	选权最小且不形成环的边	选连接已到达集与未到达集的最小权边
关键数据结构	并查集（Union-Find）	优先队列（Priority Queue）
边处理顺序	全局排序后依次考虑	每次只考虑当前顶点的邻接边
中间结构	维护一个森林（多棵树）	维护一棵树（始终连通）
二叉堆实现	$O (E l g V)$ （排序瓶颈）	$O (E l g V)$
最优实现	$O (E l g V)$ （排序始终是瓶颈）	$O (E + V l g V)$ （斐波那契堆）
邻接矩阵实现	$O (V^{2} l g V)$	$O (V^{2})$
适用场景	稀疏图（ $E = O (V)$ ）	稠密图（ $E = Ω (V^{2})$ ）
并行化潜力	较好（排序可并行）	较差（顺序扩展）
边权相同时	可能产生不同MST（取决于排序稳定性）	可能产生不同MST（取决于EXTRACT-MIN选取）
起始要求	无特殊要求	需指定起始顶点 $r$

深层联系

两种算法的本质区别在于安全边的选取方式：

Kruskal通过并查集维护连通分量，割 $(C, V - C)$ 由当前森林的连通分量自然定义。按权排序保证了被选边是该割的轻量边。
Prim通过优先队列维护未到达顶点的最小key值，割 $(S, V - S)$ 由已取出顶点集合 $S$ 定义。EXTRACT-MIN保证了被选边是该割的轻量边。

两者都正确地实现了GENERIC-MST的”不断加入安全边”策略，只是识别安全边的方式不同。从实现角度看，Kruskal更简洁（排序+并查集），Prim在稠密图上更高效（邻接矩阵 $O (V^{2})$ ）。

参见