写一个广度优先遍历的程序
时间: 2023-10-25 15:06:53 浏览: 36
当然,我可以回答你的问题。这里是一个基本的广度优先遍历(BFS)的Python程序:
```
from collections import deque
# 下面是使用邻接矩阵存储图的例子
# 你也可以用其他的数据结构,比如邻接表等等
# 图中顶点的编号从0开始
# 一个二维列表adj_matrix来存储邻接矩阵
adj_matrix = [
[0, 1, 1, 0, 0],
[1, 0, 0, 1, 1],
[1, 0, 0, 1, 0],
[0, 1, 1, 0, 1],
[0, 1, 0, 1, 0]
]
# 广度优先搜索函数
def bfs(adj_matrix, s):
n = len(adj_matrix) # 矩阵的纬度表示图的节点数
visited = [False] * n # 标记每个节点是否被访问
# 使用队列来实现BFS算法
q = deque([s])
visited[s] = True
while q:
u = q.popleft()
print(u, end=' ')
for v in range(n):
if adj_matrix[u][v] and not visited[v]:
q.append(v)
visited[v] = True
bfs(adj_matrix, 0)
```
这段代码中的adj_matrix表示一个5个节点的无向图(顶点标号分别为0、1、2、3、4),每次bfs函数的调用都输出从顶点0开始的遍历序列。