xxx 最小生成树的 Borůvka 算法 题目描述 给定一个连通无向图 \( G = (V, E) \)，其中每条边 \( e \) 有一个权重 \( w(e) \)，要求找到图的最小生成树（MST），即一个包含所有顶点的树形子图，使得所有边的权重总和最小。Borůvka 算法通过多轮迭代逐步合并连通分量来构建最小生成树，特别适合并行计算或边数较多的稀疏图。 解题过程 初始化 每个顶点初始化为一个独立的连通分量。 初始化最小生成树的边集 \( T \) 为空。 迭代过程 重复以下步骤，直到仅剩一个连通分量： a. 为每个分量选择最小边 遍历每个连通分量，找到连接该分量与外部顶点的权重最小的边（称为“安全边”）。 注意：需避免选择已在 \( T \) 中的边，且需确保边的两个端点属于不同分量。 b. 添加边并合并分量 将步骤 (a) 中找到的所有安全边加入 \( T \)。 根据这些边合并对应的连通分量（使用并查集数据结构高效管理）。 注意：同一轮中可能选择多条边，需确保合并操作不形成环（因边连接不同分量，自然无环）。 终止与输出 当所有顶点合并为一个连通分量时，\( T \) 中的边构成最小生成树。 返回 \( T \) 及其总权重。 关键点说明 并查集优化 ：使用路径压缩和按秩合并，使查找与合并操作接近常数时间。 避免重复边 ：每轮中可能选中同一条边两次（例如从两个分量均选中），需去重。 复杂度 ：每轮至少使分量数减半，故最多 \( O(\log V) \) 轮；每轮遍历所有边，总复杂度为 \( O(E \log V) \)。 示例演示 （简要） 假设图有顶点 \( \{A,B,C,D\} \) 和边 \( (A,B,1), (B,C,2), (C,D,3), (D,A,4) \)： 初始：分量 \( \{A\}, \{B\}, \{C\}, \{D\} \)。 第1轮：各分量最小边为 \( (A,B,1), (B,C,2), (C,D,3) \)（去重后），合并为 \( \{A,B\}, \{C,D\} \)，\( T = \{(A,B,1), (C,D,3)\} \)。 第2轮：分量 \( \{A,B\} \) 选 \( (B,C,2) \)，分量 \( \{C,D\} \) 选同一边，合并为单一分量，\( T \) 加入 \( (B,C,2) \)。 输出：\( T = \{(A,B,1), (B,C,2), (C,D,3)\} \)，总权重6。 通过以上步骤，Borůvka 算法以高效且并行的方式逐步构建最小生成树。