Borůvka 算法实现
Borůvka 算法的并查集实现,含调用示例和实现细节。时间 O(m log n),空间 O(n + m) · 标签 图论 / 最小生成树 / Borůvka / 并查集 / 实现
本页只放实现;算法思想与正确性见 Borůvka 算法。
使用约定
- 边用 0-index 的
vector<Edge>表示,Edge{u, v, w}。 - 返回 MST 的总权值;图不连通时返回
-1。 - 边权用
long long。
实现
struct DSU {
vector<int> fa, sz;
explicit DSU(int n) : fa(n), sz(n, 1) {
iota(fa.begin(), fa.end(), 0);
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
fa[b] = a;
sz[a] += sz[b];
return true;
}
};
struct Edge {
int u, v;
long long w;
};
long long boruvka(int n, const vector<Edge>& edges) {
DSU dsu(n);
long long ans = 0;
int components = n;
while (components > 1) {
vector<int> best(n, -1); // 每个根的最小出边下标
for (int i = 0; i < (int)edges.size(); ++i) {
int ru = dsu.find(edges[i].u);
int rv = dsu.find(edges[i].v);
if (ru == rv) continue;
if (best[ru] == -1 || edges[i].w < edges[best[ru]].w) best[ru] = i;
if (best[rv] == -1 || edges[i].w < edges[best[rv]].w) best[rv] = i;
}
bool merged = false;
for (int root = 0; root < n; ++root) {
if (best[root] == -1) continue;
const Edge& e = edges[best[root]];
if (dsu.unite(e.u, e.v)) {
ans += e.w;
--components;
merged = true;
}
}
if (!merged) return -1; // 图不连通
}
return ans;
}调用示例
int n, m;
cin >> n >> m;
vector<Edge> edges(m);
for (auto& e : edges) {
cin >> e.u >> e.v >> e.w;
--e.u;
--e.v;
}
cout << boruvka(n, edges) << '\n';实现细节
- 每一轮都要重新初始化
best,不能沿用上一轮的结果。 best按并查集的根下标存储,更新前必须find。- 同一条边可能同时是两个连通块的最小出边;靠
unite的返回值避免重复计数。 - 自环在
ru == rv时跳过;重边保留最小值即可。 - 某一轮没有任何可合并的边时,说明图不连通,返回
-1。 - 时答案是 0,循环不会进入。
- 边权和答案用
long long。 - 不需要排序;每轮直接扫描边表。
复杂度
| 步骤 | 复杂度 | 说明 |
| 每轮扫边 | 每条边两次 find | |
| 轮数 | 连通块数量至少减半 | |
| 总计 | 空间 |
对应例题
- 洛谷 P3366:【模板】最小生成树
- XOR-MST(CF 888G,Borůvka 思想 + 字典树)
- Rectilinear MST(每轮用扫描线找最近邻)