Prim算法与Boruvka算法的核心差异有哪些？

二者都是求解最小生成树（MST）的经典贪心算法，核心差异主要集中在贪心策略、适用场景、实现逻辑三个维度：

1. 核心贪心逻辑不同 #

• Prim算法：单连通分量逐步扩张。初始时随机选一个节点作为初始连通分量，每次迭代仅选择一条连接当前连通分量和外部未加入节点的最小权重边，将对应节点并入连通分量，直到所有节点都被包含。全程只维护一个正在扩张的连通分量。
• Boruvka算法：多连通分量并行合并。初始时每个节点都是独立的连通分量，每一轮迭代中所有现存的连通分量各自选出一条连接其他分量的最小权重边，同步完成分量合并，直到整个图只剩一个连通分量。全程会同时处理多个独立的连通分量。

2. 适用场景差异明显 #

• Prim算法更适配稠密图：朴素实现（邻接矩阵+暴力选最小边）的时间复杂度为O(V²)，在节点规模小、边密度极高的场景下，常数比Kruskal、Boruvka都小，效率更高；即便用优先队列优化到O(ElogV)，在稠密图下的表现也优于另外两种算法。它没有天然并行性，适合单机小规模计算。
• Boruvka算法更适配稀疏图、分布式计算场景：算法本身每一轮的分量最小边选择可以完全并行处理，不需要维护全局的优先队列或者边排序结果，现在工业界的大规模分布式MST计算几乎都是基于Boruvka改造的，比如超大规模通信网络、电力网络的规划场景。时间复杂度为O(ElogV)，如果边权范围有限还可以进一步优化到近似线性，在边权唯一的场景下不需要额外处理冲突，实现效率更高。

3. 实现复杂度与依赖不同 #

• Prim算法实现门槛更低：不需要额外的并查集结构，只需要维护两个数组：一个记录每个未加入节点到当前连通分量的最小距离，一个记录节点是否已经加入MST，逻辑非常简洁，不容易出错。
• Boruvka算法需要额外依赖并查集来管理连通分量，每一轮迭代还要处理冲突：比如两个分量同时选中了同一条边作为各自的最小出边，需要避免重复将这条边加入MST；如果存在多条权值相同的边，还要额外判断避免生成环，边界处理逻辑更复杂。

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