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数组中找到环的起点和终点，输出环的顶点序列。

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

python判断一个有向图是否有环

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

首先，我们需要定义一个辅助函数来判断从当前节点开始的深度遍历是否存在环。假设给定的有向图表示为邻接表adj，visited表示节点是否被访问过的数组，stack表示当前遍历路径上的节点。

具体步骤如下：

1. 初始化visited和stack数组，将起始节点标记为已访问，并将起始节点放入stack中。

2. 遍历stack数组中的所有节点：

- 取出stack数组的顶部元素top。

- 遍历top的所有邻接节点adj_node：

- 如果adj_node已经被访问过，那么说明存在环，返回True。

- 如果adj_node未被访问过，则将adj_node标记为已访问，并将其放入stack中。

3. 如果遍历完stack数组后没有发现环，返回False。

以下是Python代码示例：

def has_cycle(adj):
    visited = [False] * len(adj)
    stack = []

    for i in range(len(adj)):
        if not visited[i]:
            if dfs(adj, visited, stack, i):
                return True

    return False

def dfs(adj, visited, stack, node):
    visited[node] = True
    stack.append(node)

    for adj_node in adj[node]:
        if visited[adj_node]:
            return True
        elif dfs(adj, visited, stack, adj_node):
            return True

    stack.remove(node)
    return False

通过调用has_cycle函数，并传入表示有向图的邻接表，即可判断该图是否存在环。如果返回True，则存在环；如果返回False，则不存在环。

注意：该算法并不适用于有权图，仅适用于没有权重的有向图。