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

广度优先搜索（BFS）是一种图遍历算法，它从给定的起始节点开始遍历图，逐层地向外扩展搜索，直到找到目标节点或遍历完整张图。BFS通常使用队列来实现，它的基本思想是：先将起始节点加入队列，然后从队列中取出一个节点，将其所有未访问过的邻居节点加入队列，标记这些邻居节点为已访问，然后继续从队列中取出下一个节点，重复以上步骤，直到队列为空。

下面是一个使用Python实现BFS的例子，假设我们有一个无向图，用邻接表表示如下：

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

我们从节点A开始进行BFS，代码如下：

from collections import deque

def bfs(graph, start):
    visited = set() # 用集合来保存已访问过的节点
    queue = deque([start]) # 用双端队列来实现BFS
    visited.add(start) # 将起始节点标记为已访问
    while queue:
        node = queue.popleft() # 取出队列中的第一个节点
        print(node, end=' ')
        for neighbor in graph[node]: # 遍历当前节点的所有邻居节点
            if neighbor not in visited: # 如果邻居节点未被访问过
                visited.add(neighbor) # 标记邻居节点为已访问
                queue.append(neighbor) # 将邻居节点加入队列

bfs(graph, 'A') # 输出：A B C D E F