编程实现:输入图的邻接矩阵,然后用BFS遍历图
时间: 2023-08-04 22:38:03 浏览: 46
以下是Python实现:
```python
from collections import deque
def bfs(adj_matrix, start):
# 初始化队列和visited集合
queue = deque([start])
visited = set([start])
# 遍历队列中的每个节点
while queue:
node = queue.popleft()
print(node, end=' ')
# 遍历当前节点的邻居节点
for neighbor, is_connected in enumerate(adj_matrix[node]):
if is_connected and neighbor not in visited:
# 将未访问过的邻居节点加入队列和visited集合
queue.append(neighbor)
visited.add(neighbor)
# 测试
adj_matrix = [[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]]
bfs(adj_matrix, 0)
```
输出结果为:`0 1 2 3`,表示从节点0开始,按照BFS的顺序遍历了整个图。其中,邻接矩阵表示的图为:
```
0 --- 1
| \ |
| \ |
| \ |
2 --- 3
```