请用Python实现bfs
时间: 2024-06-01 10:07:16 浏览: 13
BFS(Breadth First Search),即广度优先搜索算法,是图论中的一种算法。它从图的某个顶点开始,先遍历当前顶点的所有邻接点,然后遍历这些邻接点的所有邻接点,依此类推,直到图中所有可达的顶点都被遍历一遍。在搜索过程中,使用队列来保存待访问的顶点。
以下是使用Python实现BFS的代码:
```
from collections import deque
def bfs(graph, start):
visited = set() # 用集合记录已访问过的节点
queue = deque([start]) # 将起始节点加入队列
visited.add(start) # 标记起始节点为已访问
while queue:
node = queue.popleft() # 取出队首节点
print(node) # 输出当前节点
for neighbor in graph[node]: # 遍历当前节点的邻居节点
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')
```
上述代码使用了双端队列deque来实现队列操作,使用集合set来记录已访问过的节点。在测试代码中,我们定义了一个图,以字典的形式表示每个节点的邻居节点,然后从'A'节点开始进行BFS遍历。