如果有向图中存在圈,则将所找到的圈的顶点序列依次输出,否则输出“无”
时间: 2024-03-06 09:49:21 浏览: 27
在有向图中找环可以使用深度优先搜索(DFS)来解决。
具体做法是,在进行 DFS 遍历时,使用一个 `visited` 数组记录每个节点是否被访问过,以及一个 `stack` 栈记录当前遍历路径上的节点。如果在遍历时发现当前节点已经在 `stack` 栈中出现,那么说明找到了一个环,可以输出环的路径。
以下是一个简单的 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXN 1000
bool visited[MAXN];
bool stack[MAXN];
int graph[MAXN][MAXN];
int n;
bool dfs(int u, int *path_len, int *path) {
visited[u] = true;
stack[u] = true;
path[(*path_len)++] = u;
for (int v = 0; v < n; v++) {
if (graph[u][v]) {
if (!visited[v]) {
if (dfs(v, path_len, path)) {
return true;
}
} else if (stack[v]) {
// found a cycle
printf("Cycle found: ");
for (int i = *path_len - 1; i >= 0; i--) {
printf("%d ", path[i]);
if (path[i] == v) {
break;
}
}
printf("\n");
return true;
}
}
}
stack[u] = false;
(*path_len)--;
return false;
}
void find_cycle() {
int path[MAXN], path_len = 0;
for (int u = 0; u < n; u++) {
if (!visited[u]) {
if (dfs(u, &path_len, path)) {
return;
}
}
}
printf("无\n");
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
find_cycle();
return 0;
}
```
其中,`visited` 数组记录节点是否被访问过,`stack` 数组记录当前路径上的节点是否出现过,`graph` 是邻接矩阵表示的有向图,`n` 表示节点数。
调用 `find_cycle()` 即可找到图中的一个环,如果不存在环则输出 "无"。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)