用c++实现克鲁斯卡尔算法
时间: 2023-11-25 09:50:17 浏览: 80
克鲁斯卡尔算法是一种用于求解最小生成树的贪心算法,其基本思想是将所有边按照权值从小到大排序,然后依次加入到生成树中,如果加入该边不会形成环,则将该边加入生成树中。下面是用C++实现克鲁斯卡尔算法的示例代码:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
const int MAXM = 100005;
struct Edge {
int u, v, w;
} e[MAXM];
int fa[MAXN];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
bool cmp(Edge a, Edge b) {
return a.w < b.w;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
sort(e + 1, e + m + 1, cmp);
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
int cnt = 0, ans = 0;
for (int i = 1; i <= m; i++) {
int u = e[i].u, v = e[i].v, w = e[i].w;
int fu = find(u), fv = find(v);
if (fu != fv) {
fa[fu] = fv;
cnt++;
ans += w;
if (cnt == n - 1) break;
}
}
cout << ans << endl;
return 0;
}
```
阅读全文