无向图分别采用邻接矩阵和邻接表存储,设计算法实现图的广度优先遍历,并验证下图从

1号节点开始的广度优先遍历结果。

邻接矩阵实现的算法步骤如下：

创建一个队列，并将起始节点放入队列中。
标记起始节点已经被访问。
从队列中取出第一个节点，并打印该节点。
遍历该节点的所有未被访问的邻居节点，并标记它们已经被访问，并将其放入队列中。
重复步骤3和4，直到队列为空。

邻接表实现的算法步骤与邻接矩阵实现的算法步骤类似，只是在遍历每个节点的邻居节点时需要遍历该节点的邻接表中存储的所有节点。
下面是邻接矩阵实现的Python代码实现：
from queue import Queue

def bfs_adj_matrix(adj_matrix, start):
n = len(adj_matrix)
visited = [False] * n
q = Queue()
q.put(start)
visited[start] = True
while not q.empty():
node = q.get()
print(node, end=' ')
for i in range(n):
if adj_matrix[node][i] and not visited[i]:
q.put(i)
visited[i] = True

# 测试
adj_matrix = [[0, 1, 0, 1, 0],
[1, 0, 1, 1, 1],
[0, 1, 0, 0, 1],
[1, 1, 0, 0, 1],
[0, 1, 1, 1, 0]]
bfs_adj_matrix(adj_matrix, 0) # 从1号节点开始遍历
登录后复制
输出结果为：0 1 3 2 4
下面是邻接表实现的Python代码实现：
from queue import Queue

def bfs_adj_list(adj_list, start):
n = len(adj_list)
visited = [False] * n
q = Queue()
q.put(start)
visited[start] = True
while not q.empty():
node = q.get()
print(node, end=' ')
for neighbor in adj_list[node]:
if not visited[neighbor]:
q.put(neighbor)
visited[neighbor] = True

# 测试
adj_list = {0: [1, 3],
1: [0, 2, 3, 4],
2: [1, 4],
3: [0, 1, 4],
4: [1, 2, 3]}
bfs_adj_list(adj_list, 0) # 从1号节点开始遍历
登录后复制
输出结果为：0 1 3 2 4