广度优先 python

广度优先搜索(Breadth-First Search, BFS)是一种用于遍历或寻找图或树中节点的算法。在Python中，BFS通常通过队列数据结构来实现，因为队列遵循先进先出(FIFO)原则，非常适合当前节点的所有邻居加入队列，然后逐个处理它们。

以下是使用Python实现BFS的基本步骤：

1. 创建一个空的队列，并将起始节点(源节点)放入队列。
2. 定义一个集合或字典来存储已经访问过的节点，防止重复访问。
3. 当队列非空时，执行循环：
a. 弹出队首节点。
b. 检查该节点是否是你正在查找的目标节点，如果是，则搜索结束。
c. 如果不是目标，将该节点的所有未访问邻居添加到队列的末尾，并标记为已访问。
4. 循环结束后如果没有找到目标节点，说明图中不存在这样的路径。

下面是一个简单的示例，展示如何在无向图中从给定起点找最短路径：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")  # 打印已访问节点
        
        for neighbor in graph[vertex]:  # 遍历相邻节点
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 示例用法
graph = {'A': ['B', 'C'],
         'B': ['D', 'E'],
         'C': ['F'],
         'D': [],
         'E': ['F'],
         'F': []}
bfs(graph, 'A')