图的广度优先搜索python
时间: 2023-08-15 13:10:11 浏览: 40
以下是Python实现的图的广度优先搜索(BFS)的代码:
```python
from queue import Queue
# 图的表示,使用字典类型
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
# BFS算法实现
def bfs(graph, start):
visited = set() # 使用一个集合记录已访问的节点
q = Queue() # 使用队列来实现BFS
q.put(start)
visited.add(start)
while not q.empty():
node = q.get()
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
q.put(neighbor)
visited.add(neighbor)
# 测试代码
bfs(graph, 'A')
```
这里我们以一个字典类型来表示图,其中每个键表示节点,对应的值是一个列表,表示和该节点相邻的节点。
在BFS算法实现中,我们使用了一个集合`visited`来记录已经访问过的节点,使用一个队列`q`来存储当前需要访问的节点。首先将起始节点放入队列中,并将其加入到已访问的集合中。然后不断从队列中取出节点进行访问,对于每个节点,遍历其所有邻居节点,如果邻居节点没有被访问过,则将其加入到队列中,并将其加入到已访问的集合中。重复这个过程直到队列为空,即可完成BFS搜索。