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。
  • 𝑛=1 时答案是 0,循环不会进入。
  • 边权和答案用 long long。
  • 不需要排序;每轮直接扫描边表。

复杂度

步骤复杂度说明
每轮扫边𝑂(𝑚𝛼(𝑛))每条边两次 find
轮数𝑂(log𝑛)连通块数量至少减半
总计𝑂(𝑚log𝑛)空间 𝑂(𝑛+𝑚)

对应例题

  • 洛谷 P3366:【模板】最小生成树
  • XOR-MST(CF 888G,Borůvka 思想 + 字典树)
  • Rectilinear MST(每轮用扫描线找最近邻)
源码位置