邻接表广度优先遍历

邻接表广度优先遍历（BFS）是一种用于图形搜索的算法，它对每个节点的所有邻居进行遍历，然后对每个邻居的所有邻居进行遍历，以此类推。这种遍历方式最终会覆盖所有的节点，同时保证从起始节点到其他所有节点的最短路径。

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

1. 创建一个队列，将起始节点入队。
2. 标记起始节点为已访问。
3. 从队列中取出队首节点，访问该节点并将其未访问的邻居入队。
4. 标记已访问的节点不能再次入队。
5. 重复步骤3和步骤4，直到队列为空。

下面是一个示例代码实现：

from collections import deque

# 邻接表
adj_list = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B', 'H'],
    'F': ['C'],
    'G': ['C'],
    'H': ['E']
}

# 广度优先遍历函数
def bfs(start):
    visited = set()  # 记录已访问的节点
    queue = deque([start])  # 创建队列，并将起始节点入队

    while queue:  # 当队列非空时
        node = queue.popleft()  # 取出队首节点
        if node not in visited:
            visited.add(node)  # 标记已访问的节点
            print(node, end=' ')
            for neighbor in adj_list[node]:
                if neighbor not in visited:
                    queue.append(neighbor)  # 将未访问的邻居入队

# 测试
bfs('A')

输出结果为：A B C D E F G H。