xxx 最小生成树问题（Borůvka算法）

题目描述
给定一个连通无向图，每条边都有一个正权重，要求找到一棵最小生成树（MST），即连接所有顶点的树，且其边的总权重最小。Borůvka算法是一种基于贪心策略的并行算法，适用于稀疏图。

解题过程

1. 初始化

   • 每个顶点初始时视为一个独立的连通分量（即每个顶点是一个子树）。
   • 最小生成树的边集初始为空。

2. 迭代过程
   重复以下步骤，直到只剩一个连通分量（即所有顶点连通）：
   a. 为每个连通分量选择最小边：

   • 遍历当前所有连通分量。
   • 对每个连通分量，找到所有连接该分量与外部顶点的边中权重最小的一条（若有多条最小边，任选其一）。
   • 记录这些最小边（可能重复选择同一条边，需去重）。
     b. 添加边并合并连通分量：
   • 将选中的边加入最小生成树边集。
   • 合并这些边连接的连通分量（使用并查集或标记法管理合并过程）。
     c. 更新连通分量数量：合并后，更新当前连通分量总数。

3. 终止条件

   • 当连通分量数量减为1时，算法结束。此时边集即为最小生成树。

举例说明
假设无向图顶点为{A, B, C, D}，边及权重：

• A-B: 1
• B-C: 2
• C-D: 3
• D-A: 4
• A-C: 5

步骤：

1. 初始：4个分量{A}, {B}, {C}, {D}。
2. 第一轮迭代：
   • 分量{A}的最小边：A-B(1)（连接{B}）。
   • 分量{B}的最小边：B-A(1)（同A-B，重复）。
   • 分量{C}的最小边：C-B(2)（连接{B}）或C-D(3)（连接{D}），选C-B(2)。
   • 分量{D}的最小边：D-C(3)（连接{C}）。
   • 去重后添加的边：A-B(1), C-B(2), D-C(3)。
   • 合并后新分量：{A,B,C,D}（所有顶点已连通）。
3. 算法结束，生成树边为A-B、B-C、C-D，总权重6。

关键点

• 每轮迭代可并行处理各连通分量的最小边选择。
• 需用并查集高效管理分量合并与查询。
• 时间复杂度为O(E log V)，其中E为边数，V为顶点数。