C语言完整实现利用邻接矩阵储存有向图利用DFS判断有向图是否有环,如果有环将环的顶点序列依次输出
时间: 2023-12-15 11:05:48 浏览: 82
好的,我来回答你的问题。
对于利用邻接矩阵储存有向图,我们可以定义一个二维数组来表示。假设我们有n个顶点,那么该数组就是一个n x n的矩阵。如果顶点i到顶点j有一条有向边,那么邻接矩阵中第i行第j列的值为1,否则为0。
下面是利用DFS判断有向图是否有环,并输出环的顶点序列的C语言代码:
```c
#include <stdio.h>
#define MAX_N 100
int n; // 顶点数
int graph[MAX_N][MAX_N]; // 邻接矩阵
int visited[MAX_N]; // 标记每个顶点是否被访问过
int path[MAX_N]; // 记录DFS路径上的顶点
int top = -1; // path栈顶指针
// DFS遍历有向图
int dfs(int v) {
visited[v] = 1;
path[++top] = v; // 将v加入path中
for (int i = 0; i < n; i++) {
if (graph[v][i]) {
if (!visited[i]) {
if (dfs(i)) {
return 1;
}
} else {
// 如果i已经被访问过,且在path路径上,说明有环
for (int j = top; j >= 0; j--) {
if (path[j] == i) {
printf("%d", i);
for (int k = j + 1; k <= top; k++) {
printf(" -> %d", path[k]);
}
printf(" -> %d\n", i);
return 1;
}
}
}
}
}
top--; // 回溯时将v从path中删除
return 0;
}
int main() {
// TODO: 从文件或控制台读入n和graph
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i);
}
}
return 0;
}
```
代码中,我们使用visited数组来标记每个顶点是否被访问过,path数组用来记录DFS路径上的顶点。在DFS遍历过程中,如果访问到了一个已经被访问过的顶点i,且i在path路径上,说明有环。我们就可以从path数组中找到环的起点和终点,输出环的顶点序列。
当然,这只是一个简单的实现,实际应用中还需要考虑很多细节和边界情况。
阅读全文