克鲁斯卡尔最小生成树的C++代码
时间: 2023-12-30 09:44:13 浏览: 33
以下是使用克鲁斯卡尔算法求最小生成树的C++代码:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
// 边的结构体,包含起点、终点和边权值
struct Edge {
int u, v, w;
};
const int MAXN = 1005; // 最大点数
Edge edges[MAXN]; // 存储所有边的数组
int father[MAXN]; // 并查集数组,用于判断连通性
// 比较两条边的权值,按从小到大排序
bool cmp(Edge a, Edge b) {
return a.w < b.w;
}
// 并查集查找祖先节点
int find(int x) {
if (father[x] == x) return x;
return father[x] = find(father[x]);
}
int main() {
int n, m; // 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, cmp);
// 初始化并查集数组
for (int i = 1; i <= n; i++) {
father[i] = i;
}
int ans = 0; // 最小生成树的边权值之和
int count = 0; // 已加入最小生成树的边数
for (int i = 0; i < m; i++) {
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
int fu = find(u), fv = find(v); // 查找u和v的祖先节点
if (fu != fv) { // 如果u和v不在同一连通块中
father[fu] = fv; // 将u所在连通块合并到v所在连通块中
ans += w; // 将该边加入最小生成树
count++;
if (count == n - 1) break; // 已经加入n-1条边,最小生成树已完成
}
}
cout << ans << endl; // 输出最小生成树的边权值之和
return 0;
}
```
该代码使用了并查集来判断连通性,并按边权值从小到大排序后逐条加入最小生成树中。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)