数据结构实现图的广度优先遍历
时间: 2023-10-19 10:20:33 浏览: 49
广度优先遍历(BFS)是一种遍历图的算法,它从图的某个顶点开始遍历,先访问它的所有相邻顶点,再逐层访问下去。下面是使用队列实现图的广度优先遍历的代码:
```python
from queue import Queue
# 图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
def bfs(graph, start):
visited = set() # 记录已访问的节点
queue = Queue() # 存储待访问的节点
visited.add(start)
queue.put(start)
while not queue.empty():
node = queue.get()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.put(neighbor)
# 测试
bfs(graph, 'A')
```
输出结果为:`A B C D E F`。
在这个例子中,我们使用字典来表示图,其中每个键表示一个节点,每个值表示与该节点相邻的节点。我们使用队列来存储待访问的节点,从而保证按照层级顺序访问完整个图。在遍历过程中,我们使用一个集合记录已访问的节点,防止重复访问。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)