python 有向图环路查找算法

Python 中可以使用深度优先搜索 (DFS) 和拓扑排序 (Topological Sorting) 两种算法来查找有向图中的环路。

1. DFS 算法：

在 DFS 中，我们遍历整个图，并且记录每个点的访问状态。当我们遍历到一个已经被访问过的点时，意味着我们找到了一个环路。

以下是一个基于 DFS 的有向图环路查找算法的 Python 代码：

def has_cycle(graph):
    visited = set()
    for node in graph:
        if node not in visited:
            if dfs(graph, node, visited):
                return True
    return False

def dfs(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            if dfs(graph, neighbor, visited):
                return True
        else:
            return True
    visited.remove(node)
    return False

2. 拓扑排序算法：

拓扑排序是一种对有向无环图 (DAG) 进行排序的算法。如果有向图中存在环路，则无法进行拓扑排序。

以下是一个基于拓扑排序的有向图环路查找算法的 Python 代码：

def has_cycle(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    queue = [node for node in graph if in_degree[node] == 0]
    visited = set(queue)
    while queue:
        node = queue.pop(0)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                visited.add(neighbor)
    return len(visited) != len(graph)

以上就是 Python 中两种基本的有向图环路查找算法。如果您需要更加高效的实现，建议使用 Tarjan 算法或 Kosaraju 算法。