如何实现广度优先搜索遍历

广度优先搜索遍历是一种基于队列实现的遍历算法，它从根节点开始，逐层向下遍历整个树或图结构，直到找到目标节点或遍历完所有节点为止。以下是广度优先搜索遍历的基本思路和实现步骤：

1. 创建一个空队列并将根节点入队。

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

a. 弹出队首节点，并将其标记为已访问。

b. 遍历该节点的所有邻居节点，如果邻居节点未被访问过，则将其入队。

3. 如果队列为空，表示遍历结束，可以返回结果。

广度优先搜索遍历的时间复杂度为 O(V+E)，其中V和E分别是图的节点数和边数。下面是一个示例代码实现：

def bfs_traversal(graph, root):
    visited = set() # 用集合记录已访问的节点
    queue = [root] # 创建一个队列并将根节点入队
    visited.add(root)

    while queue:
        node = queue.pop(0) # 弹出队首节点
        print(node)

        # 遍历所有邻居节点
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor) # 将邻居节点入队

在这个代码实现中，我们使用了一个集合记录已访问的节点，确保每个节点只会被访问一次，避免重复访问。同时，我们使用一个队列来存储待访问的节点，保证了广度优先的遍历顺序。