示例图

广度优先搜索（BFS）是一种图论中常用的遍历算法，用于从一个顶点开始，以层序的方式访问图中的所有顶点,以下是使用广度优先搜索实现图的遍历的步骤：

1. 初始化：

   • 创建一个邻接表来存储图的结构。
   • 初始化一个队列，通常使用collections.deque来实现。
   • 创建一个标记数组visited,用于记录已访问的顶点。

2. 遍历：

   • 将根节点（起始点）添加到队列中。
   • 标记根节点为已访问。
   • 进入循环，执行以下步骤：
     • 取出队列中的第一个元素（即根节点）。
     • 遍历根节点的所有邻居。
     • 对于每个邻居，如果未被访问过：
       • 标记邻居为已访问。
       • 将邻居添加到队列中。

3. 终止条件：

   当队列为空时,遍历过程结束。

示例代码：

from collections import deque
import sys
def bfs(graph, start):
    visited = [False] * len(graph)
    queue = deque()
    queue.append(start)
    visited[start] = True
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
    return visited
graph = [
    [],                  # 顶点
    [1, 2],               # 顶点1
    [, 3],               # 顶点2
    [1, 2],               # 顶点3
]
# 初始化
visited = bfs(graph, 0)
print("BFS遍历结果：", visited)

解释代码：

• graph是一个邻接表，每个索引对应一个顶点，其值是一个列表,表示该顶点的邻居。
• visited数组记录每个顶点是否被访问过。
• queue用于存储需要处理的顶点，使用deque实现队列。
• popleft()从队列中取出第一个元素。

输出结果：

BFS遍历结果：[True, True, True, True]

这表示从顶点开始的广度优先搜索遍历了所有顶点。