编写一个bfs的python代码
时间: 2024-03-02 18:43:41 浏览: 16
以下是一个基本的BFS(广度优先搜索)算法的 Python 代码:
```
from collections import deque
def bfs(graph, start):
visited = set() # 用集合存储已访问的节点
queue = deque([start]) # 将起始节点加入队列
visited.add(start) # 标记起始节点为已访问
while queue: # 队列不为空时
vertex = queue.popleft() # 取出队列中的第一个节点
print(vertex) # 打印当前节点
for neighbor in graph[vertex]: # 遍历当前节点的邻居节点
if neighbor not in visited: # 如果邻居节点未被访问过
visited.add(neighbor) # 标记邻居节点为已访问
queue.append(neighbor) # 将邻居节点加入队列
```
其中,`graph` 表示图的邻接表,`start` 表示起始节点。在算法执行过程中,将起始节点加入队列 `queue` 中,然后重复执行以下步骤:
1. 取出队列中的第一个节点 `vertex`;
2. 打印当前节点 `vertex`;
3. 遍历当前节点的邻居节点 `neighbor`;
4. 如果邻居节点未被访问过,则标记为已访问,并将其加入队列 `queue` 中。
重复执行以上步骤,直到队列为空为止。整个算法的时间复杂度为 O(V+E),其中 V 表示节点数,E 表示边数。