Python中使用DFS判断图(Graph)是否为DAG(Directed Acyclic Graph)

def is_dag(graph):
    """
    判断有向图是否为DAG
    :param graph: 有向图
    :return: True表示是DAG，False表示不是DAG
    """
    visited = set()  # 记录已访问过的节点
    stack = set()  # 记录在当前DFS路径中的节点
    for node in graph:
        if node not in visited:
            if dfs(node, visited, stack, graph):
                return False
    return True


def dfs(node, visited, stack, graph):
    """
    深度优先搜索
    :param node: 当前搜索的节点
    :param visited: 已访问过的节点集合
    :param stack: 在当前DFS路径中的节点集合
    :param graph: 图
    :return: True表示存在环，False表示不存在环
    """
    visited.add(node)
    stack.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            if dfs(neighbor, visited, stack, graph):
                return True
        elif neighbor in stack:
            return True
    stack.remove(node)
    return False


# 示例
graph1 = {
    'a': ['b', 'c'],
    'b': ['c', 'd'],
    'c': [],
    'd': ['a']
}
print(is_dag(graph1))  # False：存在环a->b->d->a

graph2 = {
    1: [2, 3],
    2: [4, 5],
    3: [5],
    4: [],
    5: []
}
print(is_dag(graph2))  # True：无环

graph3 = {
    'pidan': ['code', 'programming'],
    'code': ['python'],
    'programming': []
}
print(is_dag(graph3))  # True：无环