xxx 最小生成树的Borůvka算法 题目描述 给定一个连通无向图 \( G = (V, E) \)，其中每条边 \( e \in E \) 有一个权重 \( w(e) \)。要求找到图 \( G \) 的一棵最小生成树（MST），即一个包含所有顶点的连通无环子图，且其边的总权重最小。Borůvka算法是一种用于求解最小生成树问题的贪心算法，特别适合处理边数较多的稠密图或并行计算场景。 解题过程 Borůvka算法的核心思想是分阶段逐步合并连通分量（初始时每个顶点自成一个分量），每阶段为每个连通分量选择一条连接该分量与其他分量的最小权重边（称为“最小出边”），并将这些边加入MST，同时合并对应的连通分量。重复此过程直至只剩一个连通分量。 步骤详解 初始化 每个顶点初始化为一个独立的连通分量（即 \( |V| \) 个分量）。 MST的边集 \( T \) 初始为空。 循环合并连通分量 当连通分量数量大于1时，重复以下步骤： a. 为每个分量寻找最小出边 ： 遍历所有边，对于每条边 \( (u, v) \)，若 \( u \) 和 \( v \) 属于不同连通分量，则比较该边权重与这两个分量当前记录的最小出边权重。 为每个分量维护其连接其他分量的最小权重边（记录边的端点及权重）。 注意：一条边可能被两个分量同时选为候选（如边 \( (u, v) \) 可能同时是 \( u \) 所在分量和 \( v \) 所在分量的候选），但需避免重复添加。 b. 添加边并合并分量 ： 将本阶段所有分量选择的最小出边加入 MST 边集 \( T \)（需去重，因一条边可能被两个分量选中）。 使用并查集（Union-Find）数据结构合并这些边连接的连通分量，更新分量数量。 终止条件 当连通分量数量降为1时，说明所有顶点已连通，算法结束。此时 \( T \) 即为最小生成树的边集。 示例说明 考虑一个简单图，顶点集 \( V = \{A, B, C, D\} \)，边及权重如下： \( (A, B, 1) \), \( (A, C, 3) \), \( (A, D, 4) \) \( (B, C, 2) \), \( (B, D, 5) \), \( (C, D, 6) \) 执行过程 ： 阶段1 ： 初始4个分量：\{A\}, \{B\}, \{C\}, \{D\}。 各分量的最小出边： \{A\}：选边 \( (A, B, 1) \)（权重最小）。 \{B\}：选边 \( (A, B, 1) \)（权重最小）。 \{C\}：选边 \( (B, C, 2) \) 或 \( (A, C, 3) \)（选权重更小的 \( (B, C, 2) \)）。 \{D\}：选边 \( (A, D, 4) \)（权重最小）。 添加边 \( (A, B, 1) \) 和 \( (B, C, 2) \)、\( (A, D, 4) \) 到 MST（注意 \( (A, B, 1) \) 只加一次）。 合并分量：\{A, B\}, \{C\} 合并为 \{A, B, C\}；\{D\} 与 \{A, B, C\} 合并为 \{A, B, C, D\}（通过边 \( (A, D, 4) \)）。 剩余1个分量，算法结束。MST包含边 \( (A, B, 1) \)、\( (B, C, 2) \)、\( (A, D, 4) \)，总权重为7。 算法特点 时间复杂度 ：每阶段连通分量数至少减半，最多 \( O(\log |V|) \) 阶段。每阶段遍历所有边，总复杂度 \( O(|E| \log |V|) \)。 优势 ：适合并行化，因每阶段各分量的最小出边可独立计算。 关键点 ：使用并查集高效管理分量合并，避免成环。