通过实例解释什么是广度优先搜索算法?

广度优先搜索算法是一种用于图形数据结构中的遍历算法。它从图的起始顶点开始,依次访问其相邻的顶点,并记录下每个顶点的访问顺序。然后再以同样的方式访问每个相邻顶点的未访问的相邻顶点,直到整张图被访问完毄。这种遍历方式类似于水波纹的扩散,因此称为“广度优先搜索”。广度优先搜索算法通常以队列的数据结构进行实现,用于存储待访问的顶点。这种算法能够找出两个顶点之间的最短路径,或者在树结构中搜索特定节点。以下是广度优先搜索算法的示例:

# Python示例代码
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

# 使用示例
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

print(bfs(graph, 'A'))  # 输出:{'A', 'B', 'C', 'D', 'E', 'F'}