用c++写克鲁斯卡尔算法
时间: 2023-12-22 09:17:46 浏览: 18
下面是使用C++语言实现的Kruskal算法代码:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int u, v, w;
Edge(int a, int b, int c) {
u = a;
v = b;
w = c;
}
};
bool cmp(const Edge &a, const Edge &b) {
return a.w < b.w;
}
class DisjointSet {
public:
vector<int> parent, rank;
DisjointSet(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 unite(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py) return;
if (rank[px] < rank[py]) {
parent[px] = py;
} else if (rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[py] = px;
rank[px]++;
}
}
};
class Kruskal {
public:
int n;
vector<Edge> edges;
Kruskal(int n) {
this->n = n;
}
void addEdge(int u, int v, int w) {
edges.push_back(Edge(u, v, w));
}
vector<Edge> mst() {
sort(edges.begin(), edges.end(), cmp);
DisjointSet ds(n);
vector<Edge> tree;
for (int i = 0; i < edges.size(); i++) {
Edge e = edges[i];
if (ds.find(e.u) != ds.find(e.v)) {
ds.unite(e.u, e.v);
tree.push_back(e);
}
}
return tree;
}
};
int main() {
Kruskal k(5);
k.addEdge(0, 1, 2);
k.addEdge(0, 3, 6);
k.addEdge(1, 2, 3);
k.addEdge(1, 3, 8);
k.addEdge(1, 4, 5);
k.addEdge(2, 4, 7);
k.addEdge(3, 4, 9);
vector<Edge> tree = k.mst();
for (int i = 0; i < tree.size(); i++) {
printf("%d - %d : %d\n", tree[i].u, tree[i].v, tree[i].w);
}
return 0;
}
```
这是一个简单的Kruskal实现,可以添加边然后计算最小生成树。这个实现使用了一个自定义的DisjointSet类来实现并查集。