克鲁斯卡尔最小生成树算法C++代码
时间: 2023-07-22 10:57:38 浏览: 117
下面是克鲁斯卡尔最小生成树算法的C++代码示例:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 边的结构体
struct Edge {
int src, dest, weight;
};
// 并查集的结构体
struct Subset {
int parent, rank;
};
// 比较函数,用于按边的权重进行排序
bool compare(Edge a, Edge b) {
return a.weight < b.weight;
}
// 查找操作,寻找元素所属集合的根节点
int find(vector<Subset>& subsets, int i) {
if (subsets[i].parent != i) {
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
// 合并操作,将两个集合进行合并
void unionSet(vector<Subset>& subsets, int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
}
else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
}
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// 克鲁斯卡尔最小生成树算法
void kruskalMST(vector<Edge>& edges, int V) {
vector<Edge> result; // 存储最小生成树的边
// 按照边的权重进行排序
sort(edges.begin(), edges.end(), compare);
vector<Subset> subsets(V);
for (int i = 0; i < V; i++) {
subsets[i].parent = i;
subsets[i].rank = 0;
}
int e = 0; // 用于控制结果数组的下标
int i = 0; // 用于控制排序后的边数组的下标
while (e < V - 1 && i < edges.size()) {
Edge nextEdge = edges[i++];
int x = find(subsets, nextEdge.src);
int y = find(subsets, nextEdge.dest);
if (x != y) {
result.push_back(nextEdge);
unionSet(subsets, x, y);
e++;
}
}
// 输出最小生成树的边及其权重
cout << "最小生成树的边:" << endl;
for (int i = 0; i < result.size(); i++) {
cout << result[i].src << " - " << result[i].dest << ",权重:" << result[i].weight << endl;
}
}
int main() {
int V, E;
cout << "请输入顶点数:";
cin >> V;
cout << "请输入边数:";
cin >> E;
vector<Edge> edges(E);
for (int i = 0; i < E; i++) {
cout << "请输入第 " << i + 1 << " 条边的起点、终点和权重:";
cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
}
kruskalMST(edges, V);
return 0;
}
```
这段代码实现了克鲁斯卡尔最小生成树算法,通过输入顶点数和边数,然后逐条输入边的起点、终点和权重,最后输出最小生成树的边及其权重。注意,该代码中使用了并查集来判断是否形成环路,并使用了排序算法进行边的排序。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)