最小生成树kruskal算法C++代码
时间: 2024-05-05 09:14:34 浏览: 27
最小生成树Kruskal算法是一种常用的图算法,用于找到一个连通图的最小生成树。下面是Kruskal算法的C++代码示例:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义边的结构体
struct Edge {
int src, dest, weight;
};
// 定义并查集的数据结构
classFind {
public:
vector<int> parent, rank;
UnionFind(int n) {
parent.resize(n);
rank.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unionSet(int x, int y {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
};
// Kruskal算法实现
vector<Edge> kruskalMST(vector<Edge>& edges, int V) {
// 按照边的权重进行排序
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});
vector<Edge> result;
UnionFind uf(V);
for (const Edge& edge : edges) {
int src = edge.src;
int dest = edge.dest;
// 判断加入边后是否形成环路
if (uf.find(src) != uf.find(dest)) {
uf.unionSet(src, dest);
result.push_back(edge);
}
}
return result;
}
int main() {
int V, E;
cout << "请输入顶点数和边数:";
cin >> V >> E;
vector<Edge> edges(E);
cout << "请输入每条边的起点、终点和权重:" << endl;
for (int i = 0; i < E; i++) {
cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
}
vector<Edge> mst = kruskalMST(edges, V);
cout << "最小生成树的边:" << endl;
for (const Edge& edge : mst) {
cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl;
}
return 0;
}
```