用python写一个bfs代码
时间: 2023-06-01 08:03:21 浏览: 152
以下是一个基本的BFS(广度优先搜索)代码实现,可以用Python语言编写:
```python
from collections import deque
# BFS function
def bfs(graph, start):
# Create a queue for BFS
queue = deque([start])
# Create a set to keep track of visited vertices
visited = set([start])
while queue:
# Dequeue a vertex from queue
vertex = queue.popleft()
print(vertex)
# Get all adjacent vertices of the dequeued vertex
for neighbor in graph[vertex]:
# If neighbor has not been visited, mark it as visited and enqueue it
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Graph representation using adjacency list
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
# Driver code
print("BFS Traversal starting from vertex A:")
bfs(graph, 'A')
```
上面的代码中,我们首先创建了一个队列(使用deque),并将起始顶点放入队列中。同时,我们还创建了一个集合(使用set),以跟踪访问过的顶点。
在while循环中,我们首先从队列中取出一个顶点(使用popleft方法),并将其打印出来。然后,我们遍历该顶点的所有邻居,并将它们加入队列中,如果它们尚未被访问过的话。
最后,我们使用示例图中的邻接列表表示图,并从顶点A开始运行BFS。运行结果应该是:A B C D E F。
这是一个基本的BFS代码示例,可以根据需要进行修改和扩展。
阅读全文