python实现广度优先搜索

在Python中，广度优先搜索（Breadth-First Search，简称BFS）是一种用于遍历或搜索树或图的数据结构算法。它的基本思想是从起点开始，按照层级顺序依次访问每个节点，直到找到目标节点或者遍历完整个图。

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

1. **初始化队列**：创建一个空的队列，并将起始节点添加进去。

2. **标记节点**：用一个集合或字典记录已经访问过的节点，防止重复访问。

3. **循环**：进入一个循环，只要队列不为空就继续。
- **弹出队首节点**：获取队列的第一个元素，这是当前层的最后一个节点。
- **访问节点**：对这个节点执行所需的操作，比如打印或更新数据。
- **添加邻居到队列**：将该节点的所有未访问邻居加入队列的末尾，这代表它们将是下一层的节点。

4. **结束条件**：当目标节点被访问到或者队列为空时，退出循环。

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()  # 弹出队首节点
        if node not in visited:
            print(node)  # 访问节点
            visited.add(node)
            
            # 添加所有邻居到队列
            neighbors = graph[node]
            for neighbor in neighbors:
                if neighbor not in visited:
                    queue.append(neighbor)

# 示例：一个简单的邻接列表表示图
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs(graph, 'A')