请通过C++使用kruskal算法编程实现最小生成树
时间: 2023-06-19 14:08:26 浏览: 130
下面是使用C++实现Kruskal算法求最小生成树的代码:
```c++
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, m;
int fa[maxn];
struct node {
int u, v, w;
}e[maxn];
bool cmp(node a, node b) {
return a.w < b.w;
}
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) fa[fx] = fy;
}
int kruskal() {
int ans = 0, cnt = 0;
for (int i = 1; i <= n; i++) fa[i] = i;
sort(e + 1, e + m + 1, cmp);
for (int i = 1; i <= m; i++) {
int u = e[i].u, v = e[i].v, w = e[i].w;
if (find(u) != find(v)) {
merge(u, v);
ans += w;
cnt++;
if (cnt == n - 1) break;
}
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
}
printf("%d\n", kruskal());
return 0;
}
```
使用时,输入n和m分别表示图的节点数和边数,然后输入m个三元组(u, v, w),表示从u到v有一条边权为w的边。输出最小生成树的权值和。
阅读全文