C语言实现利用DFS判断无向图是否有环,如果有环将环的顶点序列依次输出
时间: 2024-02-20 10:59:42 浏览: 22
好的,针对你的问题,我可以给出以下C语言代码实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_N 1000
int n, m;
int head[MAX_N], to[MAX_N << 1], nxt[MAX_N << 1], cnt = 0;
bool vis[MAX_N], flag = false;
int path[MAX_N], top = 0; // 记录环的路径
void add_edge(int u, int v) {
to[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
}
void dfs(int u, int pre) {
vis[u] = true;
path[++top] = u;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v == pre) continue; // 不往回搜
if (vis[v]) { // 发现环
flag = true;
printf("环的顶点序列:");
for (int j = top; j >= 1; --j) {
printf("%d ", path[j]);
if (path[j] == v) break;
}
printf("%d\n", v);
return;
}
dfs(v, u);
if (flag) return; // 找到环就直接退出
}
top--; // 回溯
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
for (int i = 1; i <= n; ++i)
if (!vis[i])
dfs(i, 0);
if (!flag)
printf("该无向图没有环!\n");
return 0;
}
```
这段代码使用了 DFS 来判断无向图是否有环,如果有,则输出环的顶点序列。
代码实现的思路:
1. 使用邻接表存储无向图;
2. 对于每个连通块,从未访问的节点开始 DFS,如果发现节点已经被访问过,说明出现了环;
3. 在 DFS 的过程中,记录路径,如果发现环,就输出路径中环的部分。
希望这个回答能够回答你的问题!