Kruskal
进阶Kruskal 是贪心+并查集求最小生成树的经典方案。
// 算法讲解
Kruskal
输入节点数和带权边，观察 Kruskal 贪心选边构建 MST 的过程。
待机
速度 中
待机 ⌨1struct Edge { int u, v, w; };
2
3int kruskal(int V, vector<Edge>& edges) {
4 sort(edges.begin(), edges.end(), [](auto& a, auto& b) {
5 return a.w < b.w;
6 });
7 vector<int> parent(V);
8 iota(parent.begin(), parent.end(), 0);
9 function<int(int)> find = [&](int x) {
10 return parent[x] == x ? x : parent[x] = find(parent[x]);
11 };
12 int total = 0, cnt = 0;
13 for (auto& e : edges) {
14 int pu = find(e.u), pv = find(e.v);
15 if (pu != pv) {
16 parent[pu] = pv;
17 total += e.w;
18 if (++cnt == V - 1) break;
19 }
20 }
21 return total;
22}
复杂度分析
时间 O(E log E)
空间 O(V)
最优 O(E log E)
最坏 O(E log E)
算法讲解
Kruskal 将所有边按权值排序，从小到大依次尝试加入生成树。
如果一条边的两端已在同一并查集中，说明加入后会形成环，跳过；否则加入该边。
当已选边数达到 V-1 时，最小生成树构造完成。
时间复杂度 O(E log E)，主要由排序决定，适合稀疏图。