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

下面给出邻接矩阵和邻接表存储的广度优先遍历算法：

1. 邻接矩阵存储的广度优先遍历算法

from queue import Queue

def bfs_adj_matrix(graph, start):
    """
    邻接矩阵存储的广度优先遍历算法
    :param graph: 图的邻接矩阵表示
    :param start: 起始节点
    """
    visited = [False] * len(graph)  # 记录节点是否被访问过
    q = Queue()  # 定义队列
    q.put(start)  # 将起始节点加入队列
    visited[start] = True  # 标记起始节点为已访问

    while not q.empty():
        node = q.get()  # 取出队首节点
        print(node, end=' ')
        for i in range(len(graph)):
            if graph[node][i] == 1 and not visited[i]:  # 如果节点之间有边且未被访问过
                q.put(i)  # 将节点加入队列
                visited[i] = True  # 标记节点为已访问

2. 邻接表存储的广度优先遍历算法

from queue import Queue

def bfs_adj_list(graph, start):
    """
    邻接表存储的广度优先遍历算法
    :param graph: 图的邻接表表示
    :param start: 起始节点
    """
    visited = [False] * len(graph)  # 记录节点是否被访问过
    q = Queue()  # 定义队列
    q.put(start)  # 将起始节点加入队列
    visited[start] = True  # 标记起始节点为已访问

    while not q.empty():
        node = q.get()  # 取出队首节点
        print(node, end=' ')
        for i in graph[node]:
            if not visited[i]:  # 如果节点未被访问过
                q.put(i)  # 将节点加入队列
                visited[i] = True  # 标记节点为已访问

接下来，我们以下图为例进行验证：


使用邻接矩阵表示：

# 邻接矩阵表示
graph1 = [
    [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]
]

bfs_adj_matrix(graph1, 0)

输出结果为：`0 1 2 3 4`

使用邻接表表示：

# 邻接表表示
graph2 = [
    [1, 2],
    [0, 3, 4],
    [0, 3],
    [1, 2, 4],
    [1, 3]
]

bfs_adj_list(graph2, 0)

输出结果为：`0 1 2 3 4`

因此，验证成功，广度优先遍历算法实现正确。