直接输入邻接矩阵表示无向图,用C语言判断是否有环,并用完整代码表达
时间: 2024-02-21 18:57:28 浏览: 99
判断给定的图是不是有向无环图实例代码
5星 · 资源好评率100%
好的,下面是完整的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTEX_NUM 100
bool visited[MAX_VERTEX_NUM];
int path[MAX_VERTEX_NUM];
int path_length;
void dfs(int **graph, int vertex_num, int v, int parent) {
visited[v] = true;
path[path_length++] = v;
for (int i = 0; i < vertex_num; i++) {
if (graph[v][i] == 1) {
if (!visited[i]) {
dfs(graph, vertex_num, i, v);
} else if (i != parent) {
printf("图中存在环:");
for (int j = path_length - 1; j >= 0; j--) {
printf("%d ", path[j]);
if (path[j] == i) {
break;
}
}
printf("\n");
}
}
}
path_length--;
visited[v] = false;
}
int main() {
int vertex_num;
printf("请输入顶点数:");
scanf("%d", &vertex_num);
int **graph = (int **)malloc(vertex_num * sizeof(int *));
for (int i = 0; i < vertex_num; i++) {
graph[i] = (int *)malloc(vertex_num * sizeof(int));
}
printf("请输入邻接矩阵:\n");
for (int i = 0; i < vertex_num; i++) {
for (int j = 0; j < vertex_num; j++) {
scanf("%d", &graph[i][j]);
}
}
printf("图中是否存在环:\n");
for (int i = 0; i < vertex_num; i++) {
visited[i] = false;
}
path_length = 0;
for (int i = 0; i < vertex_num; i++) {
if (!visited[i]) {
dfs(graph, vertex_num, i, -1);
}
}
for (int i = 0; i < vertex_num; i++) {
free(graph[i]);
}
free(graph);
return 0;
}
```
在这份代码中,我们首先定义了一个邻接矩阵的二维数组graph,用于存储无向图的连接关系。然后通过malloc函数动态分配内存,读入邻接矩阵。
接着,我们使用dfs函数进行深度优先搜索,判断图中是否存在环,并输出环的顶点序列。
在dfs函数中,我们首先将当前节点标记为已访问,并将它加入到当前搜索路径中。然后,我们遍历所有与当前节点相邻的节点,如果某个节点未被访问过,就递归调用dfs函数进行搜索。如果某个节点已经被访问过,并且它不是当前搜索路径上的最后一个节点,就说明图中存在环。此时,我们可以将环的顶点序列依次输出。最后,我们将当前节点从搜索路径中移除,并将它的访问状态标记为未访问。
最后,我们使用free函数释放动态分配的内存,并返回0表示程序正常结束。
希望我的回答能够帮到您!
阅读全文