xxx 最小生成树的Borůvka算法 题目描述 ： 给定一个带权无向连通图 \( G = (V, E) \)，其中每条边 \( e \) 有一个非负权重 \( w(e) \)。要求使用 Borůvka 算法构造该图的最小生成树（MST），即一棵包含所有顶点的树，使得树上边的权重之和最小。 算法背景 ： Borůvka 算法是最早的 MST 算法之一（1926 年提出），其核心思想是分阶段迭代。每一阶段，每个连通分量选择一条连接该分量与其他分量的最小权重边，并将这些边加入 MST，同时合并连通分量。算法重复直到只剩一个连通分量。其时间复杂度为 \( O(E \log V) \)，适合处理边数较多的稀疏图。 解题步骤 ： 初始化 ： 将每个顶点视为一个独立的连通分量（即初始时有 \( |V| \) 个分量）。 初始化一个空集合 \( T \)，用于存储 MST 的边。 迭代过程 ： 当连通分量数量大于 1 时，重复以下步骤： 步骤 2.1：为每个分量找最小边 遍历所有连通分量，对每个分量 \( C_ i \)，找到所有连接 \( C_ i \) 与 其他分量 的边中权重最小的边（称为“最小外接边”）。注意：避免重复选择同一条边。 实现时，可维护一个数组 minEdge ，为每个分量记录其最小外接边及其权重。 遍历所有边 \( (u, v, w) \)：若 \( u \) 和 \( v \) 属于不同分量，则比较该边与这两个分量当前的最小外接边，更新 minEdge 。 步骤 2.2：添加边并合并分量 将本阶段所有分量的最小外接边加入集合 \( T \)（需去重，因为一条边可能被两个分量同时选为最小边）。 根据加入的边，使用并查集（Union-Find）合并连通分量：将通过最小外接边连接的分量合并为一个新分量。 步骤 2.3：更新分量数量 合并后，更新当前连通分量数量。若数量变为 1，算法终止。 输出结果 ： 集合 \( T \) 中的边构成最小生成树。 示例演示 ： 考虑一个简单图，顶点集 \( V = \{A, B, C, D\} \)，边集 \( E \) 及权重如下： \( (A,B,1) \), \( (A,C,4) \), \( (A,D,3) \) \( (B,C,2) \), \( (B,D,5) \), \( (C,D,6) \) 执行过程 ： 初始化 ：分量集合为 \( \{A\}, \{B\}, \{C\}, \{D\} \)，\( T = \emptyset \)。 阶段 1 ： 分量 \( \{A\} \) 的最小外接边：比较边 AB(1)、AC(4)、AD(3)，选 AB(1)。 分量 \( \{B\} \) 的最小外接边：比较 AB(1)、BC(2)、BD(5)，选 AB(1)（与 \( \{A\} \) 相同）。 分量 \( \{C\} \) 的最小外接边：比较 AC(4)、BC(2)、CD(6)，选 BC(2)。 分量 \( \{D\} \) 的最小外接边：比较 AD(3)、BD(5)、CD(6)，选 AD(3)。 添加边 AB、BC、AD 到 \( T \)（去重后为 AB(1)、BC(2)、AD(3)）。 合并分量：\( \{A,B\} \)（通过 AB）、\( \{C\} \) 与 \( \{A,B\} \) 通过 BC 合并为 \( \{A,B,C\} \)，\( \{D\} \) 与 \( \{A,B,C\} \) 通过 AD 合并为 \( \{A,B,C,D\} \)。 剩余 1 个分量，算法结束。 结果 ：MST 包含边 AB(1)、BC(2)、AD(3)，总权重为 6。 关键点 ： 每阶段至少减少一半的分量数量，故最多迭代 \( O(\log V) \) 次。 使用并查集高效管理分量合并（每次操作近似 \( O(1) \)）。 避免重复添加边：可通过标记边或仅在合并后更新分量实现。 Borůvka 算法在现代并行计算和分布式图处理中仍有应用，因其阶段独立性适合并行化。