Kruskal 最小生成树算法
文章目录
算法步骤:
- 所有点保留,撤掉所有的边。
- 将所有边按照边权排序。
- 不断选择边权最小的边,联通各个点。
- 当所有点联通,就完成了。
示例代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 100000; // 最大顶点数
const int MAX_M = 100000; // 最大边数
struct Edge {
int u, v, len;
}e[MAX_M];
int fa[MAX_N], n, m; // fa 数组记录了并查集中结点的父亲
bool cmp(Edge a,Edge b) {
return a.len < b.len;
}
// 并查集相关代码
void init() {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int get(int x) {
if (fa[x] == x) {
return x;
}
return fa[x] = get(fa[x]);
}
int kruskal(int n, int m) {
sort(e + 1, e + m + 1, cmp); // 对边按边权进行升序排序
init(); // 初始化并查集
int ans = 0; // 保存最小生成树上的总边权和,也就是答案
for (int i = 1; i <= m; i++) {
int fu = get(E[i].u);
int fv = get(E[i].v);
if (fu != fv) { // 合并
fa[fv] = fu;
ans += e[i].len;
}
}
return ans;
}
int main() {
cin >> n >> m; // n 为点数,m 为边数
for (int i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].len; // 用边集数组存放边,方便排序和调用
}
cout << kruskal(n, m) << endl;
return 0;
}
$$总时间复杂度: \mathcal{O}(E \log E + V\alpha (V))$$
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论