FC14 并查集判断无向图中是否存在环
正确代码
在图论中，并查集（Union-Find） 主要用于判断无向图中是否存在环。对于有向图，并查集 无法直接判断是否有环，因为有向图的环涉及到拓扑顺序，而并查集不记录方向信息。
✅ 本回答将包括：
- 并查集的基本实现（C语言）
- 使用并查集判断无向图是否有环
- 邻接矩阵存储
- 邻接表存储
- 说明：为什么并查集不能用于有向图
- 有向图判环的替代方法（拓扑排序）
- 完整可运行 C 代码示例
一、并查集基本结构（C语言）
| C |
|---|
| #include <stdio.h>
#include <stdlib.h>
// 并查集结构
typedef struct {
int *parent;
int *rank; // 用于按秩合并
int n;
} UnionFind;
// 初始化并查集
UnionFind* createUnionFind(int n) {
UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
uf->n = n;
uf->parent = (int*)malloc(n * sizeof(int));
uf->rank = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
uf->parent[i] = i;
uf->rank[i] = 0;
}
return uf;
}
// 查找（带路径压缩）
int find(UnionFind* uf, int x) {
if (uf->parent[x] != x) {
uf->parent[x] = find(uf, uf->parent[x]);
}
return uf->parent[x];
}
// 合并（按秩合并）
void unionSets(UnionFind* uf, int x, int y) {
int rootX = find(uf, x);
int rootY = find(uf, y);
if (rootX == rootY) return;
if (uf->rank[rootX] < uf->rank[rootY]) {
uf->parent[rootX] = rootY;
} else if (uf->rank[rootX] > uf->rank[rootY]) {
uf->parent[rootY] = rootX;
} else {
uf->parent[rootY] = rootX;
uf->rank[rootX]++;
}
}
// 判断是否连通
int isConnected(UnionFind* uf, int x, int y) {
return find(uf, x) == find(uf, y);
}
// 释放内存
void destroyUnionFind(UnionFind* uf) {
free(uf->parent);
free(uf->rank);
free(uf);
}
|
二、无向图判环（使用并查集）
原理
- 遍历每一条边
(u, v)
- 如果
find(u) == find(v)，说明 u 和 v 已经连通，再加这条边会形成环
- 否则，
union(u, v)
1. 邻接矩阵存储的无向图
| C |
|---|
| // 判断邻接矩阵表示的无向图是否有环
int hasCycle_undirected_matrix(int **matrix, int n) {
UnionFind* uf = createUnionFind(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) { // 避免重复边
if (matrix[i][j] == 1) { // 存在边
if (isConnected(uf, i, j)) {
destroyUnionFind(uf);
return 1; // 发现环
}
unionSets(uf, i, j);
}
}
}
destroyUnionFind(uf);
return 0; // 无环
}
|
注意：无向图邻接矩阵对称，只遍历上三角避免重复。
2. 邻接表存储的无向图
| C |
|---|
| // 邻接表节点
typedef struct Node {
int vertex;
struct Node* next;
} Node;
// 图结构
typedef struct {
int n;
Node** adjList;
} GraphList;
// 创建节点
Node* createNode(int v) {
Node* node = (Node*)malloc(sizeof(Node));
node->vertex = v;
node->next = NULL;
return node;
}
// 创建邻接表图
GraphList* createGraphList(int n) {
GraphList* graph = (GraphList*)malloc(sizeof(GraphList));
graph->n = n;
graph->adjList = (Node**)calloc(n, sizeof(Node*));
return graph;
}
// 添加无向边
void addEdge(GraphList* graph, int u, int v) {
Node* node = createNode(v);
node->next = graph->adjList[u];
graph->adjList[u] = node;
node = createNode(u);
node->next = graph->adjList[v];
graph->adjList[v] = node;
}
// 判断邻接表表示的无向图是否有环
int hasCycle_undirected_list(GraphList* graph) {
UnionFind* uf = createUnionFind(graph->n);
for (int u = 0; u < graph->n; u++) {
Node* node = graph->adjList[u];
while (node != NULL) {
int v = node->vertex;
if (u < v) { // 避免重复处理同一条边
if (isConnected(uf, u, v)) {
destroyUnionFind(uf);
return 1;
}
unionSets(uf, u, v);
}
node = node->next;
}
}
destroyUnionFind(uf);
return 0;
}
|
三、有向图不能用并查集判环的原因
并查集只维护连通性，不维护方向。
例如：
- 有向边 A → B 和 B → C，不会形成环
- 但有向边 A → B 和 B → A 形成环（2环）
- 并查集无法区分这两个情况，因为它们都连接 A 和 B
❌ 并查集不能检测有向图中的环
四、有向图判环的正确方法：拓扑排序（DFS 或 Kahn 算法）
我们使用 DFS + 状态标记 来判断有向图是否有环。
状态说明：
0: 未访问1: 正在访问（在 DFS 栈中）2: 已完成访问
| C |
|---|
| // DFS 判断有向图是否有环（邻接表）
int dfs_cycle_directed(GraphList* graph, int u, int* visited) {
visited[u] = 1; // 正在访问
Node* node = graph->adjList[u];
while (node != NULL) {
int v = node->vertex;
if (visited[v] == 1) return 1; // 发现后向边，有环
if (visited[v] == 0 && dfs_cycle_directed(graph, v, visited))
return 1;
node = node->next;
}
visited[u] = 2; // 完成访问
return 0;
}
int hasCycle_directed_list(GraphList* graph) {
int* visited = (int*)calloc(graph->n, sizeof(int));
for (int i = 0; i < graph->n; i++) {
if (visited[i] == 0) {
if (dfs_cycle_directed(graph, i, visited)) {
free(visited);
return 1;
}
}
}
free(visited);
return 0;
}
|
同理，邻接矩阵的有向图也可以用类似 DFS 实现。
五、完整测试代码示例
| C |
|---|
| #include <stdio.h>
#include <stdlib.h>
// [前面所有代码粘贴在此]
int main() {
int n = 4;
// ============ 无向图测试（邻接矩阵） ============
int **matrix = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
matrix[i] = (int*)calloc(n, sizeof(int));
}
// 添加边：0-1, 1-2, 2-0 → 形成环
matrix[0][1] = matrix[1][0] = 1;
matrix[1][2] = matrix[2][1] = 1;
matrix[2][0] = matrix[0][2] = 1;
printf("无向图（邻接矩阵）是否有环: %s\n",
hasCycle_undirected_matrix(matrix, n) ? "是" : "否");
// ============ 无向图测试（邻接表） ============
GraphList* graph = createGraphList(n);
addEdge(graph, 0, 1);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
// addEdge(graph, 3, 0); // 加这行会成环
printf("无向图（邻接表）是否有环: %s\n",
hasCycle_undirected_list(graph) ? "是" : "否");
// ============ 有向图测试（邻接表） ============
GraphList* dgraph = createGraphList(n);
// 0->1, 1->2, 2->0 → 环
Node* n0 = createNode(1); dgraph->adjList[0] = n0;
Node* n1 = createNode(2); dgraph->adjList[1] = n1;
Node* n2 = createNode(0); dgraph->adjList[2] = n2;
printf("有向图（邻接表）是否有环: %s\n",
hasCycle_directed_list(dgraph) ? "是" : "否");
return 0;
}
|
六、总结
| 图类型 |
存储方式 |
是否可用并查集判环 |
推荐方法 |
| 无向图 |
邻接矩阵 |
✅ 是 |
并查集 |
| 无向图 |
邻接表 |
✅ 是 |
并查集 |
| 有向图 |
邻接矩阵/表 |
❌ 否 |
DFS / 拓扑排序 |
七、图示说明（mermaid）
graph TD
A[开始] --> B{图类型}
B -->|无向图| C[使用并查集]
B -->|有向图| D[使用DFS拓扑排序]
C --> E[遍历每条边]
E --> F{两端是否已连通?}
F -->|是| G[发现环]
F -->|否| H[合并两个集合]
D --> I[DFS遍历]
I --> J{遇到正在访问的节点?}
J -->|是| G
J -->|否| K[继续遍历]
✅ 结论：
- 并查集仅适用于无向图判环
- 有向图必须使用DFS 或 Kahn 算法进行拓扑排序判环
如需完整 .c 文件，可告知，我可打包提供。