编程实现:输入图的邻接矩阵, 然后用 BFS遍历图。
时间: 2024-03-15 11:44:55 浏览: 51
好的,以下是 Python 代码实现:
```python
from collections import deque
# 输入邻接矩阵,返回 BFS 遍历结果
def bfs(adj_matrix):
n = len(adj_matrix) # 图的节点数
visited = [False] * n # 标记每个节点是否已经访问过
queue = deque() # 用 deque 实现队列
res = [] # BFS 遍历结果
# 对每个节点进行 BFS 遍历
for i in range(n):
if not visited[i]:
visited[i] = True
queue.append(i)
while queue:
cur_node = queue.popleft()
res.append(cur_node)
# 将当前节点未访问过的邻居加入队列
for j in range(n):
if adj_matrix[cur_node][j] and not visited[j]:
visited[j] = True
queue.append(j)
return res
```
其中,`adj_matrix` 是邻接矩阵,如果节点 i 和节点 j 之间有边相连,则 `adj_matrix[i][j]` 为 1,否则为 0。`bfs(adj_matrix)` 函数返回 BFS 遍历结果,即所有节点的遍历顺序。