Boruvka与Kruskal算法求解MST的差异及共性探讨

刚好我对这两个最小生成树算法挺熟悉的，先给你理清楚它们的共性，再拆解最核心的差异点：

两者的核心共性 #

• 都能在无向图中求解最小生成树（MST）
• 同属贪心算法家族，核心逻辑都是通过不断向现有树结构中添加权重最小的有效边，最终生成完整的MST
• 都是基于全局遍历图中边的思路来构建MST，和Prim算法那种从单个节点出发、逐个拓展节点的局部拓展方式完全不同

最关键的差异：选边的核心逻辑 #

这是两者最本质的区别，完全是两种不同的“选边策略”：

• Kruskal算法：先把图中所有边按权重从小到大排序，然后按顺序逐个检查每条边——只要这条边连接的两个节点不在同一个连通分量里（也就是加入后不会形成环），就把它纳入MST。简单说就是“按边的优先级排队，挨个试，能加就加”。
• Boruvka算法：它的出发点是每个连通分量（初始状态下每个节点都是独立的分量），每个分量会找到自己能连接到其他分量的权重最小的那条边，然后将这条边加入MST，同时把两个分量合并成一个新的分量。重复这个过程，直到所有分量合并为一个完整的MST。可以通俗理解为“每个小团队各自找最便宜的外联通道，然后合并团队，直到变成一个大团队”。

另外补充个小细节：Boruvka的这种分量独立选边的特性，让它在处理大规模图或者分布式计算场景时更有优势，因为各个分量的选边操作可以并行进行；而Kruskal更依赖边的排序步骤，在边数相对较少的图中表现更直接。

内容的提问来源于stack exchange，提问作者User12547645