有向无环图的深度优先遍历和广度优先遍历怎么做？

有向无环图（Directed Acyclic Graph，简称DAG）是一种没有环的有向图。深度优先遍历（Depth-First Search，简称DFS）和广度优先遍历（Breadth-First Search，简称BFS）是两种常见的图遍历算法。以下是这两种算法的实现方法：

### 深度优先遍历（DFS）

深度优先遍历是一种递归的图遍历方法。它会尽可能深地搜索图的分支，直到不能再深入为止，然后回溯。

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

### 广度优先遍历（BFS）

广度优先遍历是一种逐层搜索的方法。它会先访问所有邻居节点，然后再逐层向下访问。

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        print(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

### 使用示例

假设我们有一个有向无环图，可以用字典来表示：

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print("DFS Traversal:")
dfs(graph, 'A')

print("\nBFS Traversal:")
bfs(graph, 'A')

### 解释

1. **DFS**：从起始节点开始，访问其所有邻居节点。对于每个邻居节点，递归地访问其邻居节点，直到所有节点都被访问。
2. **BFS**：从起始节点开始，先访问所有邻居节点，然后逐层向下访问。每层节点都被访问完后，再访问下一层的节点。

这两种方法都可以有效地遍历有向无环图，但它们的访问顺序不同。DFS更适用于需要找到某种路径或检测环的情况，而BFS则更适用于需要找到最短路径的情况。