kruskal算法代码实现c++
时间: 2023-09-28 13:07:15 浏览: 64
Kruskal算法是一种最小生成树算法,可以用来求无向图的最小生成树。下面是基于并查集实现的C++代码:
```c++
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m;
int f[MAXN], sz[MAXN]; // 并查集数组
struct Edge {
int u, v, w;
} e[MAXN];
bool cmp(Edge a, Edge b) { return a.w < b.w; } // 边按权值排序
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); } // 并查集查找
void merge(int x, int y) { // 并查集合并
int fx = find(x), fy = find(y);
if (fx != fy) {
if (sz[fx] > sz[fy]) swap(fx, fy);
f[fx] = fy;
sz[fy] += sz[fx];
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) f[i] = i, sz[i] = 1;
for (int i = 1; i <= m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
sort(e + 1, e + m + 1, cmp);
int cnt = 0, ans = 0;
for (int i = 1; i <= m; i++) {
if (cnt == n - 1) break; // 边数已经达到n-1条
if (find(e[i].u) == find(e[i].v)) continue; // 两个点已经在同一集合中
merge(e[i].u, e[i].v);
ans += e[i].w;
cnt++;
}
printf("%d\n", ans);
return 0;
}
```
具体实现中,我们首先定义了一个结构体`Edge`,表示一条边,包括起点、终点和边权。然后定义了并查集数组`f`和`sz`,其中`f[i]`表示第i个节点所在的集合,`sz[i]`表示第i个集合的大小。接着,我们按照边权从小到大排序,依次遍历每条边,如果两个点已经在同一集合中,就跳过,否则将两个集合合并,同时累加边权。最后输出最小生成树的权值和即可。
注意,这段代码使用了路径压缩和按秩合并等优化,可以有效加速并查集的操作。