Kruskal算法的C++实现文档
Kruskal算法是一种经典的图论算法，用于生成最小生成树。以下是一个完整的C++实现代码示例，供大家参考学习。
#include
#include
#include
using namespace std;
// 定义边结构体
struct Edge {
int src, dest, weight;
};
// 定义并查集
class UnionFind {
public:
vector parent;
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] == x)
return x;
return find(parent[x]);
}
void Union(int x, int y) {
int xset = find(x);
int yset = find(y);
parent[xset] = yset;
}
};
// Kruskal算法实现
vector kruskal(vector& edges, int v) {
// 根据权重对边进行排序
sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
return a.weight < b.weight;
});
vector result;
UnionFind uf(v);
int i = 0;
while (result.size() < v - 1) {
Edge next_edge = edges[i++];
int x = uf.find(next_edge.src);
int y = uf.find(next_edge.dest);
// 如果加入该边不会构成环路，则加入最小生成树
if (x != y) {
result.push_back(next_edge);
uf.Union(x, y);
}
}
return result;
}
int main() {
// 定义图的顶点数和边
int v = 5;
vector edges = {
{0, 1, 2},
{0, 4, 6},
{1, 2, 3},
{1, 4, 5},
{2, 3, 1},
{3, 4, 4}
};
// 调用Kruskal算法求解最小生成树
vector min_spanning_tree = kruskal(edges, v);
// 输出最小生成树的边和权重
for (Edge edge : min_spanning_tree) {
cout << edge.src << " - " << edge.dest << ": " << edge.weight << endl;
}
return 0;
}
cpp
3.35KB
2023-09-03 13:01
