广度优先遍历临接表序列
时间: 2023-12-28 18:24:24 浏览: 26
广度优先遍历(BFS)是一种图形搜索算法,它从图的起点开始遍历,并逐步向外扩展遍历未访问的节点,直到遍历完所有节点。下面是广度优先遍历邻接表序列的Python实现:
```python
from collections import deque
# 定义邻接表
adj_list = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
# 定义BFS函数
def bfs(adj_list, start):
visited = set() # 用集合记录已经访问过的节点
queue = deque([start]) # 初始化队列,将起点加入队列
visited.add(start) # 标记起点为已访问
while queue: # 当队列不为空时循环
node = queue.popleft() # 取出队列头部节点
print(node, end=' ') # 输出节点
for neighbor in adj_list[node]: # 遍历当前节点的邻居节点
if neighbor not in visited: # 如果邻居节点没有被访问过
visited.add(neighbor) # 标记邻居节点为已访问
queue.append(neighbor) # 将邻居节点加入队列
# 调用BFS函数
bfs(adj_list, 'A') # 从'A'节点开始遍历
```
输出结果为:A B C D E F
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)