判断无向图中是否有环c语言
时间: 2023-12-03 13:03:27 浏览: 92
判断无向图中是否有环可以使用深度优先搜索(DFS)。
具体实现步骤如下:
1. 定义一个 bool 类型的数组 visited[] 来记录每个节点是否被访问过,初始化为 false。
2. 定义一个 int 类型的 prev[] 数组来记录每个节点的前驱节点,初始化为 -1。
3. 从任意一个未被访问过的节点开始进行 DFS 遍历。
4. 在遍历过程中,对于每个节点 u 的邻居节点 v,如果 v 已被访问过且不是 u 的前驱节点,则说明存在环,返回 true。
5. 如果遍历完成后没有找到环,则返回 false。
以下是 C 语言代码实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAXN 100
int n; // 图中节点数
bool G[MAXN][MAXN]; // 图的邻接矩阵
bool visited[MAXN]; // 节点访问标记
int prev[MAXN]; // 前驱节点
bool dfs(int u, int p) {
visited[u] = true;
prev[u] = p;
for (int v = 0; v < n; v++) {
if (G[u][v]) {
if (!visited[v]) {
if (dfs(v, u)) {
return true; // 子图中存在环
}
} else if (v != p) {
return true; // 存在环
}
}
}
return false; // 不存在环
}
bool hasCycle() {
for (int i = 0; i < n; i++) {
visited[i] = false;
prev[i] = -1;
}
for (int u = 0; u < n; u++) {
if (!visited[u]) {
if (dfs(u, -1)) {
return true; // 子图中存在环
}
}
}
return false; // 不存在环
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int w;
scanf("%d", &w);
G[i][j] = (w != 0);
}
}
if (hasCycle()) {
printf("Yes\n");
} else {
printf("No\n");
}
return 0;
}
```
其中,dfs() 函数是递归实现的深度优先搜索,返回值为当前子图是否存在环。hasCycle() 函数遍历整个图,判断是否存在环。prev[] 数组用于记录每个节点的前驱节点,判断是否存在“回溯”边。