有向无环图的判定DFS

有向无环图（DAG）是一种特殊的有向图，其中不存在任何环路。判断一个有向图是否为DAG，可以采用DFS算法。

DFS算法的基本思路是从一个起点开始，沿着一条路径不断深入，直到无法继续深入为止，然后回溯到上一个节点，再选择另一条路径继续深入。如果在深入的过程中遇到了已经访问过的节点，那么说明存在环路。

对于一个有向图，我们可以记录每个节点的状态，分为三种：

1. 未访问过的节点
2. 正在访问的节点
3. 已经访问过的节点

在DFS算法中，当我们遍历到一个节点时，将其状态设置为“正在访问”，然后遍历其所有邻居节点。如果邻居节点的状态为“正在访问”，那么说明存在环路，直接返回false。如果邻居节点的状态为“未访问过”，那么继续遍历该节点的邻居节点。当一个节点的所有邻居节点都遍历完成后，将其状态设置为“已经访问过”，并将其入栈。

最后，如果所有节点都被遍历过，且不存在环路，那么返回true。

下面是DFS判定DAG的代码实现：

def is_dag(graph):
    visited = [0] * len(graph)
    stack = []
    
    def dfs(node):
        visited[node] = 1
        for neighbor in graph[node]:
            if visited[neighbor] == 1:
                return False
            elif visited[neighbor] == 0:
                if not dfs(neighbor):
                    return False
        visited[node] = 2
        stack.append(node)
        return True
    
    for node in range(len(graph)):
        if visited[node] == 0:
            if not dfs(node):
                return False
    
    return True

其中，graph是一个邻接表，表示有向图的连接情况。visited数组记录每个节点的状态，0表示未访问过，1表示正在访问，2表示已经访问过。stack数组用于记录访问完成的节点，最后可以根据stack数组还原出DAG的拓扑排序结果。