Kruskal 算法实现

Kruskal 算法的并查集实现,含调用示例和实现细节。

时间 O(m log m),空间 O(n + m) · 标签 图论 / 最小生成树 / Kruskal / 并查集 / 实现

本页只放实现;算法思想与正确性见 Kruskal 算法。

使用约定

  • 边用 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 kruskal(int n, vector<Edge>& edges) {
  sort(edges.begin(), edges.end(),
       [](const Edge& a, const Edge& b) { return a.w < b.w; });

  DSU dsu(n);
  long long ans = 0;
  int used = 0;

  for (const auto& e : edges) {
    if (!dsu.unite(e.u, e.v)) continue;
    ans += e.w;
    if (++used == n - 1) break;
  }

  return used == n - 1 ? ans : -1;  // -1 表示图不连通
}

调用示例

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 << kruskal(n, edges) << '\n';

实现细节

  • 并查集初始化要覆盖全部顶点;输入是 1-index 时注意数组大小和下标。
  • 路径压缩 + 按大小合并,保证并查集近似常数时间。
  • 自环不会造成问题:unite(u, u) 直接返回 false。
  • 重边不需要特判:排序后会先选较小的一条,其余自然跳过。
  • 选满 𝑛−1 条边后可以提前退出,不必扫描剩余边。
  • 𝑛=1 时答案是 0,不需要任何边。
  • 排序比较器必须是严格弱序,用 a.w < b.w,不要写 <=。
  • 边权和答案用 long long。

复杂度

步骤复杂度说明
边排序𝑂(𝑚log𝑚)主要瓶颈
并查集𝑂(𝑚𝛼(𝑛))路径压缩 + 按大小合并
总计𝑂(𝑚log𝑚)空间 𝑂(𝑛+𝑚)

对应例题

  • 洛谷 P3366:【模板】最小生成树
  • 洛谷 P1546:最短网络 Agri-Net
  • 洛谷 P1195:口袋的天空(生成森林)
  • CF 1245D:Shichikuji and Power Grid(虚拟源点)
源码位置