有向无环图的遍历

有向无环图（DAG）是一种不包含环的有向图。在DAG上进行遍历操作需要按序遍历每个节点，且必须保证对于每一条有向边(u, v)，源节点u一定要在目标节点v之前被访问。

一种常用的DAG遍历算法是拓扑排序，它可以保证所有节点都被访问且符合上述条件。具体实现如下：

1. 建立节点入度表inDegree，记录每个节点的入度（即指向该节点的边数）。
2. 将所有入度为0的节点加入一个队列Q中。
3. 当队列不为空时，取出队头节点node。
4. 遍历该节点的所有出边，对于每条边(node, neighbor)，将邻居节点neighbor的入度减1，若减1后入度变为0，则将其加入队列Q中。
5. 重复步骤3-4，直到队列为空。

遍历结束后，若访问到所有节点，则说明DAG中没有环；否则，存在环。

下面是使用Python实现拓扑排序的代码示例：

def topologicalSort(graph):
    # 计算每个节点的入度
    inDegree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            inDegree[neighbor] += 1

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

    # 依次出队并将其邻居节点的入度减1
    result = []
    while queue:
        node = queue.pop(0)
        result.append(node)
        for neighbor in graph[node]:
            inDegree[neighbor] -= 1
            if inDegree[neighbor] == 0