xxx 最小生成树的 Borůvka 算法 题目描述 给定一个连通无向图 \( G = (V, E) \)，其中每条边 \( e \in E \) 有一个权重 \( w(e) \)，要求找到图 \( G \) 的一棵最小生成树（MST），即一个包含所有顶点的连通无环子图，且所有边的权重之和最小。Borůvka 算法是一种用于求解最小生成树的高效算法，特别适合并行计算和稀疏图。 解题过程 Borůvka 算法的核心思想是分阶段进行多轮操作，每轮中每个连通分量选择一条连接该分量与其他分量的最小权重边，并将这些边加入生成树，同时合并连通分量。重复这一过程直到只剩一个连通分量。 步骤详解 初始化 将每个顶点视为一个独立的连通分量（即初始时有 \( |V| \) 个分量）。 初始化一个空集合 \( T \)，用于存储最小生成树的边。 迭代合并连通分量 当连通分量的数量大于 1 时，重复以下步骤： a. 为每个连通分量选择最小边 ： 遍历所有连通分量。对于每个连通分量 \( C \)，找到所有连接 \( C \) 与图中其他分量的边中权重最小的一条（即满足一个端点在 \( C \) 内，另一个端点不在 \( C \) 内）。 记录这些最小边（注意：一条边可能被两个分量选择，需去重）。 b. 将选择的边加入生成树 ： 将步骤 (a) 中选出的边加入集合 \( T \)（需避免重复添加同一条边）。 c. 合并连通分量 ： 根据加入的边，合并连通分量（例如使用并查集数据结构来管理分量的合并）。 更新当前连通分量的数量。 输出结果 当只剩下一个连通分量时，集合 \( T \) 中的边构成最小生成树。 示例说明 考虑一个简单图，顶点集 \( V = \{A, B, C, D\} \)，边集如下： \( (A, B) \) 权重 1 \( (B, C) \) 权重 2 \( (C, D) \) 权重 3 \( (A, D) \) 权重 4 执行过程 ： 初始状态 ：每个顶点是一个分量：\( \{A\}, \{B\}, \{C\}, \{D\} \)，\( T = \emptyset \)。 第一轮 ： 分量 \( \{A\} \) 的最小边为 \( (A, B) \)（权重 1）。 分量 \( \{B\} \) 的最小边为 \( (A, B) \)（权重 1）。 分量 \( \{C\} \) 的最小边为 \( (B, C) \)（权重 2）。 分量 \( \{D\} \) 的最小边为 \( (C, D) \)（权重 3）。 将边 \( (A, B) \)、\( (B, C) \)、\( (C, D) \) 加入 \( T \)，合并分量后得到 \( \{A, B\}, \{C, D\} \)。 第二轮 ： 分量 \( \{A, B\} \) 的最小边为 \( (B, C) \)（权重 2，连接 \( \{C, D\} \)）。 分量 \( \{C, D\} \) 的最小边为 \( (B, C) \)（权重 2，连接 \( \{A, B\} \)）。 将边 \( (B, C) \) 加入 \( T \)（已存在，无需重复添加），合并分量后得到 \( \{A, B, C, D\} \)。 结束 ：输出 \( T = \{(A, B), (B, C), (C, D)\} \)，总权重为 6。 算法特点 时间复杂度 ：\( O(E \log V) \)，其中每轮处理 \( O(E) \) 条边，最多 \( O(\log V) \) 轮（每轮后连通分量数至少减半）。 优势 ：适合并行计算，因每轮中各分量的最小边选择可独立进行。 注意事项 ：需使用并查集高效合并分量，并避免重复添加边。 通过以上步骤，Borůvka 算法逐步合并连通分量，最终构建出最小生成树。