最小生成树kruskal算法c++代码
时间: 2023-12-30 20:24:05 浏览: 39
以下是使用C++编写的Kruskal算法求解最小生成树的代码示例:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义边的结构体
struct Edge {
int src, dest, weight;
};
// 定义并查集的结构体
struct DisjointSet {
int *parent, *rank;
int n;
DisjointSet(int n) {
this->n = n;
parent = new int[n];
rank = new int[n];
// 初始化每个节点的父节点为自身,秩为0
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// 查找节点的根节点
int find(int u) {
if (u != parent[u]) {
parent[u] = find(parent[u]);
}
return parent[u];
}
// 合并两个节点所在的集合
void merge(int x, int y) {
x = find(x); y = find(y);
if (rank[x] > rank[y]) {
parent[y] = x;
} else {
parent[x] = y;
if (rank[x] == rank[y]) {
rank[y]++;
}
}
}
};
// 比较边的权值,用于排序
bool compareEdges(Edge a, Edge b) {
return a.weight < b.weight;
}
// Kruskal算法求解最小生成树
vector<Edge> kruskalMST(vector<Edge> edges, int V) {
vector<Edge> result;
// 对边按照权值进行排序
sort(edges.begin(), edges.end(), compareEdges);
DisjointSet ds(V);
for (auto edge : edges) {
int srcParent = ds.find(edge.src);
int destParent = ds.find(edge.dest);
// 如果两个顶点的根节点不同,则将边加入最小生成树中
if (srcParent != destParent) {
result.push_back(edge);
ds.merge(srcParent, destParent);
}
}
return result;
}
int main() {
int V, E;
cout << "Enter the number of vertices: ";
cin >> V;
cout << "Enter the number of edges: ";
cin >> E;
vector<Edge> edges(E);
cout << "Enter the source, destination, and weight of each edge:" << endl;
for (int i = 0; i < E; i++) {
cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
}
vector<Edge> minimumSpanningTree = kruskalMST(edges, V);
cout << "Minimum Spanning Tree:" << endl;
for (auto edge : minimumSpanningTree) {
cout << edge.src << " -- " << edge.dest << " : " << edge.weight << 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)