C++Kruskal算法
时间: 2023-11-10 17:16:10 浏览: 32
Kruskal算法是一种用来求解最小生成树的贪心算法。它的基本思想是将所有的边按照权值从小到大排序,然后依次选取权值最小的边,如果这条边的两个端点不在同一个连通块中,就将它们合并成一个连通块,直到所有的点都在一个连通块中。
以下是C++实现Kruskal算法的代码:
```c++
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
struct Edge {
int u, v, w;
}edges[MAXN*MAXN];
int p[MAXN]; // 并查集数组
bool cmp(const Edge& a, const Edge& b) {
return a.w < b.w;
}
int find(int x) { // 并查集查找
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) p[i] = i; // 初始化并查集
for (int i = 0; i < m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
sort(edges, edges+m, cmp); // 对所有边按照权值排序
int cnt = 0, ans = 0;
for (int i = 0; i < m; i++) {
int u = find(edges[i].u), v = find(edges[i].v);
if (u != v) { // 如果这条边的两个端点不在同一个连通块中
p[u] = v; // 将它们合并成一个连通块
ans += edges[i].w; // 累加边权
cnt++; // 累加边数
if (cnt == n-1) break; // 已经选出了n-1条边,退出循环
}
}
cout << ans << endl; // 输出最小生成树的边权和
return 0;
}
```
Kruskal算法的时间复杂度为O(mlogm),其中m为边数。