怎么判断有向图有没有回路

有向图有回路的判断方法是使用拓扑排序算法。如果有向图存在回路，那么在拓扑排序过程中，必然存在一个点无法入队，因为它的入度始终大于0。如果所有节点都能入队，那么说明该有向图不存在回路。

具体步骤如下：

1. 统计每个节点的入度，建立一个入度表。

2. 将所有入度为0的节点入队。

3. 每次从队列中取出一个节点，将它的所有出边指向的节点的入度减1。

4. 如果某个节点的入度减到0了，就将它入队。

5. 重复步骤3和4，直到队列为空。

6. 如果所有节点都能入队，说明该有向图不存在回路；否则，存在回路。

代码示例：

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

    # 将所有入度为0的节点入队
    queue = [node for node in graph if in_degree[node] == 0]

    # 拓扑排序
    while queue:
        node = queue.pop(0)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # 如果所有节点都能入队，说明不存在回路
    return all(in_degree[node] == 0 for node in graph)

# 示例
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
print(has_cycle(graph))  # False

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': ['A']
}
print(has_cycle(graph))  # True