广度优先搜索算法 python
时间: 2024-06-26 11:01:20 浏览: 6
<<
广度优先搜索(Breadth-First Search, BFS)是一种用于遍历或搜索树和图的数据结构算法。在Python中,BFS通常使用队列(Queue)来实现,因为它按照节点的层次顺序逐层探索。
以下是BFS的基本步骤和Python代码实现:
1. 创建一个空的队列,并将起始节点添加到队列中。
2. 当队列不为空时,执行以下操作:
a. 从队列中取出一个节点。
b. 检查该节点的所有未访问邻接节点,并将它们加入队列。
c. 标记当前节点为已访问。
3. 重复步骤2,直到队列为空,表示所有可达到的节点都已被访问。
以下是一个简单的Python代码示例,假设我们有一个无向图或邻接列表表示的图:
```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)
print(vertex) # 或者执行其他操作
queue.extend(graph[vertex] - visited) # 添加未访问邻接节点到队列
# 使用示例:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A')
```