Kruskal算法用链表判断回路C++实现
时间: 2023-07-12 18:09:00 浏览: 59
Kruskal算法是一种最小生成树算法,它的基本思想是将所有的边按照权值从小到大排序,然后依次加入生成树中,如果加入该边不会导致生成树形成环,则加入该边,否则舍去该边。
在Kruskal算法中,需要判断当前加入的边是否会导致生成树形成环。可以使用并查集来实现该功能。具体来说,对于每个节点,维护它的父节点,初始时每个节点的父节点都是它本身。每次加入一条边时,判断该边的两个端点是否在同一个并查集中,如果是,则加入该边会导致生成树形成环,应该舍去该边;否则,将两个端点所在的并查集合并起来,并将该边加入生成树中。
以下是使用链表实现的Kruskal算法判断回路的C++代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
struct Edge {
int u, v, w;
Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
};
struct Node {
int parent;
int rank;
Node() : parent(-1), rank(0) {}
};
vector<Node> nodes;
// 查找节点x所在的集合的代表节点
int find(int x) {
if (nodes[x].parent == -1) {
return x;
} else {
return nodes[x].parent = find(nodes[x].parent);
}
}
// 合并x和y所在的集合
void merge(int x, int y) {
int root_x = find(x);
int root_y = find(y);
if (root_x != root_y) {
if (nodes[root_x].rank < nodes[root_y].rank) {
nodes[root_x].parent = root_y;
} else if (nodes[root_x].rank > nodes[root_y].rank) {
nodes[root_y].parent = root_x;
} else {
nodes[root_y].parent = root_x;
nodes[root_x].rank++;
}
}
}
// 判断加入边(u, v, w)是否形成环
bool hasCycle(int u, int v) {
int root_u = find(u);
int root_v = find(v);
if (root_u == root_v) {
return true;
} else {
merge(root_u, root_v);
return false;
}
}
// Kruskal算法求最小生成树
vector<Edge> kruskal(int n, vector<Edge>& edges) {
vector<Edge> result;
nodes.resize(n);
sort(edges.begin(), edges.end(), [](Edge& e1, Edge& e2) {
return e1.w < e2.w;
});
for (auto& edge : edges) {
if (!hasCycle(edge.u, edge.v)) {
result.push_back(edge);
}
}
return result;
}
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}
};
vector<Edge> result = kruskal(n, edges);
for (auto& edge : result) {
cout << edge.u << " " << edge.v << " " << edge.w << endl;
}
return 0;
}
```
以上代码中,find函数和merge函数分别实现了并查集中的查找和合并操作。hasCycle函数判断加入边(u, v, w)是否会导致生成树形成环,如果是,则返回true,否则返回false,并且将u和v所在的集合合并起来。kruskal函数实现了Kruskal算法,其中使用sort函数将所有边按照权值从小到大排序,并依次加入生成树中。最后,将生成树的边保存在result向量中,并返回。