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，则不存在环。

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