最小生成树
最小生成是无向图中的一个问题。
kruskal 算法
时间复杂度 ,m 为边的个数
- 对边进行排序。
- 用并查集处理连通性问题。
const int maxn = 1e6+1; struct E{ // 图中的边 int u, v, w; }e[maxn]; //struct edge{ // 最小生成树的边 // int to, w; // edge(){} // edge(int to, int w): to(to), w(w){} //}; vector<edge> g[maxn]; // 最小生成树边的存储 int f[maxn]; // 并查集-数组 int fd(int x) { // 并查集-查询 if (f[x] == x) return x; return f[x] = fd(f[x]); } void kruskal(int n, int m) { // 最小生成树 - kruskal 算法 for(int i = 1; i <= n; ++ i) { // 初始化 f[i] = i; g[i].clear(); } sort(e+1, e+m+1, [](E &e1, E &e2){return e1.w<e2.w;}); for(int i = 1, j = 0; i <= m; ++ i) { int a = fd(e[i].u); int b = fd(e[i].v); if (a == b) continue; // 成环 跳过 f[b] = a; // g[e[i].u].push_back(edge(e[i].v, e[i].w)); // g[e[i].v].push_back(edge(e[i].u, e[i].w)); if (++ j == n-1) break; // 树已生成 } }