C语言完整实现实现利用邻接矩阵储存无向图利用DFS判断无向图是否有环,如果有环将环的顶点序列依次输出
时间: 2024-02-21 07:56:48 浏览: 116
好的,下面是C语言完整实现实现利用邻接矩阵储存无向图利用DFS判断无向图是否有环,如果有环将环的顶点序列依次输出的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100 // 最大节点数
int graph[MAX_N][MAX_N]; // 邻接矩阵
int visited[MAX_N]; // 记录每个节点是否被访问过
int n; // 节点数
void dfs(int u, int parent, int* cycle, int* index, int* found) {
visited[u] = 1; // 标记当前节点为已访问
// 遍历当前节点的所有邻居节点
for (int v = 0; v < n; v++) {
if (graph[u][v]) { // 如果节点u和节点v之间有连边
if (visited[v] && v != parent) { // 如果节点v已经被访问过,且不是节点u的父节点
// 找到了环,将环的顶点序列依次输出
*found = 1;
cycle[*index] = v;
(*index)++;
cycle[*index] = u;
(*index)++;
return;
} else if (!visited[v]) { // 如果节点v还没有被访问过
dfs(v, u, cycle, index, found); // 继续访问节点v
if (*found) { // 如果已经找到环,将当前节点加入环中
cycle[*index] = u;
(*index)++;
return;
}
}
}
}
}
int has_cycle(int* cycle) {
int index = 0;
int found = 0;
// 对每个节点进行DFS遍历
for (int u = 0; u < n; u++) {
if (!visited[u]) {
dfs(u, -1, cycle, &index, &found);
if (found) {
cycle[index] = cycle[0]; // 环的最后一个节点应该和第一个节点相同
return 1; // 存在环
}
}
}
return 0; // 不存在环
}
int main() {
// 读入节点数和连边数
int m;
scanf("%d %d", &n, &m);
// 读入每条边的信息,并更新邻接矩阵
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u][v] = graph[v][u] = 1;
}
int cycle[MAX_N]; // 保存环的顶点序列
if (has_cycle(cycle)) {
printf("The graph has a cycle: ");
for (int i = 0; i < n; i++) {
printf("%d ", cycle[i]);
}
printf("\n");
} else {
printf("The graph does not have a cycle.\n");
}
return 0;
}
```
在这个实现中,我们首先读入节点数和连边数,然后读入每条边的信息,并更新邻接矩阵。
接着,我们调用`has_cycle`函数来判断无向图是否有环,并输出环的顶点序列。如果图中不存在环,则输出"The graph does not have a cycle."。
需要注意的是,这个实现中使用了一个全局变量`n`,表示节点数。如果您的代码中不使用全局变量,请将其改写为函数参数。
阅读全文