C++用kruskal算法实现无向图基于邻接矩阵的最大代价生成树的代码
时间: 2024-04-30 08:22:18 浏览: 14
以下是用Kruskal算法实现无向图基于邻接矩阵的最大代价生成树的代码:
```
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 10010;
int parent[MAXN], rank[MAXN];
int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
void Union(int x, int y) {
int px = Find(x), py = Find(y);
if (px == py) {
return;
}
if (rank[px] < rank[py]) {
parent[px] = py;
} else if (rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[px] = py;
rank[py]++;
}
}
struct edge {
int u, v, w;
bool operator<(const edge& e) const {
return w > e.w;
}
} edges[MAXN * MAXN];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
sort(edges, edges + m);
// 初始化并查集
for (int i = 1; i <= n; i++) {
parent[i] = i;
rank[i] = 0;
}
int ans = 0, cnt = 0;
for (int i = 0; i < m; i++) {
if (cnt == n - 1) {
break;
}
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
int pu = Find(u), pv = Find(v);
if (pu != pv) {
Union(pu, pv);
ans += w;
cnt++;
}
}
cout << ans << endl;
return 0;
}
```
补充说明:本段代码为技术交流,仅供参考,使用时请遵守相关法律、规定,如因使用本段代码引发任何法律纠纷,本人概不承担任何责任。