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。 - 重边不需要特判:排序后会先选较小的一条,其余自然跳过。
- 选满 条边后可以提前退出,不必扫描剩余边。
- 时答案是 0,不需要任何边。
- 排序比较器必须是严格弱序,用
a.w < b.w,不要写<=。 - 边权和答案用
long long。
复杂度
| 步骤 | 复杂度 | 说明 |
| 边排序 | 主要瓶颈 | |
| 并查集 | 路径压缩 + 按大小合并 | |
| 总计 | 空间 |
对应例题
- 洛谷 P3366:【模板】最小生成树
- 洛谷 P1546:最短网络 Agri-Net
- 洛谷 P1195:口袋的天空(生成森林)
- CF 1245D:Shichikuji and Power Grid(虚拟源点)