有向图的广度优先遍历

有向图的广度优先遍历（BFS）是一种图遍历算法，它从图的起始顶点开始遍历图，先访问起始顶点，然后遍历与该顶点相邻的所有顶点，再依次遍历与这些相邻顶点相邻的所有未被访问过的顶点，直到遍历完所有与起始顶点相连通的顶点。BFS通常使用队列来实现，遍历过程中将已经访问过的顶点标记为已访问，以避免重复访问。

以下是一个有向图的BFS遍历的Python实现：

from collections import defaultdict, deque

# 定义有向图类
class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    # 添加边
    def add_edge(self, u, v):
        self.graph[u].append(v)

    # BFS遍历
    def bfs(self, start):
        # 初始化队列和visited数组
        queue = deque([start])
        visited = [False] * (max(self.graph) + 1)
        visited[start] = True

        while queue:
            # 出队列
            node = queue.popleft()
            print(node, end=' ')

            # 遍历相邻节点
            for i in self.graph[node]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True

# 创建有向图对象
g = Graph()

# 添加边
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

# 从节点2开始BFS遍历
print("BFS Traversal (starting from vertex 2):")
g.bfs(2)

输出结果为：2 0 3 1