DFS判断有向图是否有环

DFS（深度优先搜索）可以用来判断有向图是否有环。

具体步骤如下：

1. 选择一个起点，从该点开始进行深度优先搜索。

2. 每次访问一个未访问过的节点时，将其标记为“已访问”。

3. 每次遍历到一个节点时，判断该节点的所有邻居节点是否已经被访问过。

4. 如果邻居节点已经被访问过，且不是当前节点的父节点，则说明有环。

5. 如果邻居节点未被访问过，则以该节点为起点，重复步骤2-4。

6. 如果所有节点都被访问过，且没有发现环，则说明该有向图无环。

具体实现可以使用递归或栈来实现。

相关问题

C语言完整实现利用邻接矩阵储存有向图利用DFS判断有向图是否有环，如果有环将环的顶点序列依次输出

好的，我来回答你的问题。

对于利用邻接矩阵储存有向图，我们可以定义一个二维数组来表示。假设我们有n个顶点，那么该数组就是一个n x n的矩阵。如果顶点i到顶点j有一条有向边，那么邻接矩阵中第i行第j列的值为1，否则为0。

下面是利用DFS判断有向图是否有环，并输出环的顶点序列的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数组中找到环的起点和终点，输出环的顶点序列。

当然，这只是一个简单的实现，实际应用中还需要考虑很多细节和边界情况。

C语言实现利用DFS判断无向图是否有环，如果有环将环的顶点序列依次输出

好的，针对你的问题，我可以给出以下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 的过程中，记录路径，如果发现环，就输出路径中环的部分。

希望这个回答能够回答你的问题！