图的遍历--广度优先搜索

### 广度优先搜索遍历算法解释

广度优先搜索（Breadth First Search, BFS）是一种用于遍历或搜索图中节点的算法。该方法按照层次顺序访问所有节点，即先访问起始节点，再依次访问其相邻的所有未被访问过的邻居节点，然后再访问这些邻居的邻居，以此类推直到所有的可达节点都被访问完毕[^1]。

对于每一个新发现的节点，将其标记为已访问并加入队列；当处理到某个节点时，则从队列移除之。通过这种方式可以确保每个节点仅会被处理一次，并且能够找到最短路径上的边数最少的一条路经到达目标节点[^2]。

#### Python 实现代码如下：

from collections import deque

def bfs(graph, start):
    visited = set()  # 记录已经访问过的顶点集合
    queue = deque([start])  # 初始化队列为起点
    
    while queue:
        vertex = queue.popleft()
        
        if vertex not in visited:
            print(f'Visiting {vertex}')
            visited.add(vertex)
            
            # 将当前顶点连接但尚未访问过的新邻接点入队
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)

# 定义无向图的数据结构表示法
graph_example = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph_example, 'A')

此段程序定义了一个简单的函数`bfs()`来执行广度优先搜索操作。给定一个由字典形式描述的图和一个起始顶点作为输入参数，在控制台打印出按层序访问各个顶点的过程。