无向图的广度优先遍历

无向图的广度优先遍历是一种图遍历算法，它从图的某个顶点开始遍历，先访问该顶点，然后依次访问该顶点的所有邻接点，再依次访问这些邻接点的邻接点，直到遍历完所有与该顶点相连通的顶点。在遍历过程中，需要记录已经访问过的顶点，避免重复访问。

以下是无向图的广度优先遍历的实现步骤：

1. 创建一个队列，用于存储待访问的顶点。
2. 从图中任意一个顶点开始遍历，将该顶点入队，并标记为已访问。
3. 从队列中取出一个顶点，访问该顶点，并将该顶点的所有未访问过的邻接点入队，并标记为已访问。
4. 重复步骤3，直到队列为空。

下面是一个示例代码，演示了如何使用广度优先遍历算法遍历无向图：

from collections import deque

# 无向图的邻接矩阵表示
graph = [
    [0, 1, 1, 0, 0],
    [1, 0, 1, 1, 0],
    [1, 1, 0, 1, 1],
    [0, 1, 1, 0, 1],
    [0, 0, 1, 1, 0]
]

# 广度优先遍历函数
def bfs(graph, start):
    visited = [False] * len(graph)  # 记录每个顶点是否被访问过
    queue = deque([start])  # 创建一个队列，用于存储待访问的顶点
    visited[start] = True  # 标记起始顶点为已访问

    while queue:
        vertex = queue.popleft()  # 取出队列中的第一个顶点
        print(vertex, end=' ')

        # 遍历该顶点的所有邻接点
        for i in range(len(graph[vertex])):
            if graph[vertex][i] == 1 and not visited[i]:
                queue.append(i)  # 将未访问过的邻接点入队
                visited[i] = True  # 标记该邻接点为已访问

# 从0号顶点开始遍历
bfs(graph, 0)