kruskal算法的c++实现
时间: 2023-11-20 21:58:19 浏览: 50
以下是Kruskal算法的C++实现,假设已经有了边集数组edges和点数n:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
struct edge {
int u, v, w;
};
bool cmp(edge a, edge b) {
return a.w < b.w;
}
int find(int x, int* parent) {
if (parent[x] == x)
return x;
return find(parent[x], parent);
}
void kruskal(edge* edges, int n, int m) {
sort(edges, edges + m, cmp);
int parent[n];
for (int i = 0; i < n; i++)
parent[i] = i;
int cnt = 0, ans = 0;
for (int i = 0; i < m && cnt < n - 1; i++) {
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
int pu = find(u, parent), pv = find(v, parent);
if (pu != pv) {
parent[pu] = pv;
ans += w;
cnt++;
}
}
cout << "Minimum Cost: " << ans << endl;
}
int main() {
int n, m;
cin >> n >> m;
edge edges[m];
for (int i = 0; i < m; i++)
cin >> edges[i].u >> edges[i].v >> edges[i].w;
kruskal(edges, n, m);
return 0;
}
```
其中,cmp函数为排序函数,按照边权值从小到大排序;find函数为并查集查找函数,用于查找x所在的连通块的根节点;kruskal函数为Kruskal算法的主体函数,使用并查集维护连通性,每次选取边权值最小的边加入生成树中。