最小生成树kruskal算法c++
时间: 2023-12-30 15:24:54 浏览: 33
以下是使用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) {
int rootX = find(x);
int rootY = find(y);
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
};
// Kruskal算法求最小生成树
void kruskal(vector<Edge>& edges, int n) {
// 按照边的权重进行排序
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});
vector<Edge> result; // 存储最小生成树的边
DisjointSet ds(n);
for (const auto& edge : edges) {
int src = edge.src;
int dest = edge.dest;
// 判断两个节点是否在同一个集合中
if (ds.find(src) != ds.find(dest)) {
result.push_back(edge);
ds.merge(src, dest);
}
}
// 输出最小生成树的顶点集合和边的集合
cout << "顶点集合:";
for (int i = 0; i < n; i++) {
cout << i << " ";
}
cout << endl;
cout << "边的集合:";
for (const auto& edge : result) {
cout << "(" << edge.src << ", " << edge.dest << ") ";
}
cout << endl;
}
int main() {
int n = 6; // 图的顶点数
// 定义图的边集合
vector<Edge> edges = {
{0, 1, 4},
{0, 2, 3},
{1, 2, 1},
{1, 3, 2},
{2, 3, 4},
{3, 4, 2},
{4, 5, 6}
};
kruskal(edges, n);
return 0;
}
```