xxx 最小生成树的Borůvka算法

题目描述
给定一个连通无向图G=(V, E)，其中每条边e∈E有一个权重w(e)。需要找到一个边的子集T⊆E，使得所有顶点通过T连通，并且总权重Σw(e)最小。这就是最小生成树（MST）问题。Borůvka算法是求解该问题的经典算法之一，特别适合处理边数较多的图。

解题过程

1. 算法思想
   Borůvka算法采用分治策略，每一轮并行处理所有连通分量（初始时每个顶点是一个分量）。在每轮中，为每个连通分量选择一条连接该分量与其他分量的最小权重边（称为"最小出边"）。将这些边加入生成树，并合并连通分量。重复此过程直到只剩一个连通分量。

2. 详细步骤

   • 步骤1：初始化
     每个顶点单独作为一个连通分量，生成树边集T初始为空。

   • 步骤2：循环处理（直到只剩1个连通分量）
     a. 为每个分量找最小出边：
     遍历所有边，对于每条边(u,v)，若u和v属于不同连通分量，则比较该边权重与u、v所在分量的当前最小出边权重，更新最小出边记录。
     注意：需避免重复选择同一条边，确保每条边只被比较一次。

     b. 添加边并合并分量：
     将本轮所有分量的最小出边加入T（需去重，因为一条边可能被两个分量同时选为最小出边）。
     用并查集（Union-Find）合并这些边连接的连通分量。

     c. 更新分量计数：
     合并后重新计算连通分量个数。若分量数＞1，则回到步骤2a。

3. 实例演示
   考虑一个5顶点图，边权重如下：
   (A,B,2), (A,C,3), (B,C,1), (B,D,4), (C,D,5), (C,E,6)

   • 第1轮：
     分量：{A}, {B}, {C}, {D}, {E}
     最小出边：A→(A,B,2), B→(B,C,1), C→(B,C,1), D→(B,D,4), E→(C,E,6)
     添加边(B,C,1), (A,B,2), (B,D,4), (C,E,6)（去重后共4条）
     合并后分量：{A,B,C,D,E}（剩余1个分量，结束）

4. 复杂度分析

   • 每轮连通分量数至少减半，故最多执行O(log|V|)轮。
   • 每轮遍历所有边O(|E|)，并用并查集操作（近似O(1)）。
   • 总复杂度：O(|E|log|V|)，适合边密集的图。

5. 关键点

   • 并查集用于高效合并分量。
   • 每轮必须去重最小出边，防止重复添加。
   • 算法天然并行，可同时处理所有分量。

总结
Borůvka算法通过多轮并行选择最小出边，逐步合并连通分量构建MST，其效率在边数较多时尤为突出。