有向图邻接表的广度优先遍历

邻接表是一种表示图的常见数据结构，它通过链表的方式存储每个顶点的相邻顶点。广度优先遍历是一种基于队列的遍历方式，从图的某一起始顶点开始，依次访问其相邻顶点，然后再依次访问相邻顶点的相邻顶点，直到遍历完整个图。

下面是邻接表的广度优先遍历的实现步骤：

1. 初始化一个队列，将起始顶点入队。

2. 初始化一个 visited 数组，用于记录每个顶点是否被访问过，将起始顶点标记为已访问。

3. 当队列不为空时，执行以下步骤：

a. 出队队头元素，并访问该顶点。

b. 遍历该顶点的所有邻接顶点，如果邻接顶点未被访问，则将其入队，并标记为已访问。

4. 重复步骤 3，直到队列为空，遍历结束。

下面是邻接表的广度优先遍历的代码实现（假设图的顶点从 0 到 n-1 编号）：

from collections import deque


def bfs(adj_list, start):
    n = len(adj_list)
    visited = [False] * n
    q = deque()
    q.append(start)
    visited[start] = True
    while q:
        v = q.popleft()
        print(v, end=' ')
        for u in adj_list[v]:
            if not visited[u]:
                q.append(u)
                visited[u] = True

其中，adj_list 是邻接表，是一个列表的列表，adj_list[i] 表示顶点 i 的邻接顶点列表。start 是起始顶点的编号。函数中使用了 Python 自带的 deque 类型实现队列。