最小生成树可并行化的 Sollin（Boruvka）算法
上期回顾：https://www.cnblogs.com/ofnoname/p/18715203在前文中，我们剖析了最小生成树（MST）问题中的两大经典算法：
[*]Kruskal 以“边权平等”为信条，通过排序与并查集自下而上聚合连通分量；
[*]Prim 以“中心辐射”为策略，通过优先队列自上而下扩张领土。
二者虽路径迥异，却殊途同归，均以贪心策略保证全局最优。还有一种不那么为人熟知的 Sollin 算法（又称 Boruvka 算法），它融合了前两者的思想，并在并行计算领域大放异彩，在特定情况下非常有用。
Sollin 算法：分治与并行
Sollin 算法仍然基于贪心，但是他从多个起点开始。想象一场战国时代的争霸赛：初始每一个点都是一代表一个国家，自身是一个连通分量，接下来每个小国（连通分量）各自派出使者，寻找与邻国间成本最低的结盟道路。所有国家同时行动，每一轮合并后形成更大的联盟，直到天下归一。Sollin 算法的核心正是这种分阶段的并行贪心策略：
具体步骤：
[*]初始化：每个节点自成一个连通分量。
[*]并行探索：每一轮迭代下，对每个连通分量，找到其连接外界的最小权重边（类似 Prim 的切割性质）。
[*]批量合并：将所有找到的最小边加入 MST，合并连通分量。
[*]循环迭代：重复步骤 2-3，直至只剩一个连通分量。
正确性证明
Sollin 的正确性同样基于安全边定理：
每个连通分量选择的最小出边，必定属于某个 MST。
归纳法视角：
[*]初始状态：每个节点独立，所有边均为安全边候选。
[*]归纳假设：当前已选边集是某个 MST 的子集。
[*]归纳步骤：每轮选择的边均为不同切割的最小边，加入后仍保持 MST 的存在性。
关键观察：
[*]若两个连通分量选择彼此之间的同一条边，该边只会被加入一次（去重机制）。
[*]合并操作保证连通分量数量至少减半，确保算法终止。
struct Edge { int u, v, weight, index;};class Graph { int n, m; vector<Edge> edges;public: Graph(int n, int m) : n(n), m(m) {} void addEdge(int u, int v, int weight, int index) { edges.push_back({u, v, weight, index}); } long long boruvka(vector<int>& result) { UnionFind uf(n); // 并查集实现略 long long total_weight = 0; int components = n; while (components > 1) { vector<Edge> min_edges(n, {-1, -1, INT_MAX, -1}); // 查找每个连通分量的最小边 for (const auto& edge : edges) { int root_u = uf.find(edge.u); int root_v = uf.find(edge.v); if (root_u == root_v) continue; if (edge.weight < min_edges.weight) min_edges = edge; if (edge.weight < min_edges.weight) min_edges = edge; } // 收集并处理有效边 unordered_set<int> valid_edges; for (int i = 0; i < n; ++i) { if (min_edges.index != -1 && !uf.connected(min_edges.u, min_edges.v)) { valid_edges.insert(min_edges.index); } } if (valid_edges.empty()) break; // 合并连通分量并记录结果 int added = 0; for (int idx : valid_edges) { const Edge& e = edges; if (uf.unite(e.u, e.v)) { total_weight += e.weight; result.push_back(idx); added++; } } if (added == 0) break; components -= added; } return components == 1 ? total_weight : -1; }};<hr>时间复杂度
[*]每轮操作成本：
[*]寻找每个连通分量的最小边：\(O(|E|)\)（需遍历所有边）。
[*]合并连通分量：使用并查集优化后接近 \(O(|V| \cdot \alpha(|V|))\)。
[*]轮数上限：由于每轮连通分量数量至少减半，总轮数为 \(O(\log |V|)\)。
[*]总复杂度：\(O(|E| \log |V|)\)，与二叉堆优化的 Prim 算法相当。
<hr>Sollin vs Kruskal
维度Sollin (Boruvka)Kruskal核心策略多连通分量并行找最小边全局排序 + 单线程并查集时间复杂度\(O(|E| \log |V|)\)\(O(|E| \log |E|)\)空间复杂度需维护多个连通分量只需存储并查集和边列表并行潜力✅ 每轮操作天然可并行（如MapReduce）❌ 排序和并查集依赖全局状态适用场景边权分布均匀的图，或需要并行处理稀疏图（\(|E| \ll |V|^2\)）实现难度较高（需处理多分量合并与去重）简单（仅排序与并查集）在分布式系统中，每轮各连通分量的最小边搜索可分配给不同计算节点，适合超大规模图（如社交网络分析）。据说 Boruvka 算法在 20 世纪 20 年代被用于规划捷克斯洛伐克的电力网络，其分阶段特性契合人工计算流程。
页:
[1]