图的构造（基于邻接矩阵存储）和BFS遍历

好的，我来为你解答图的构造和广度优先搜索遍历。

## 图的构造

图可以用邻接矩阵或邻接表来存储。这里我们介绍基于邻接矩阵的存储方式。

邻接矩阵是一个二维数组，其中元素 a[i][j] 表示节点 i 和节点 j 之间是否有边相连。如果有，则 a[i][j] 为 1；否则为 0。对于无向图，邻接矩阵是对称的；对于有向图，邻接矩阵则不一定对称。

下面是一个无向图的邻接矩阵：

0 1 0 1 0
1 0 1 1 0
0 1 0 1 1
1 1 1 0 1
0 0 1 1 0

这个邻接矩阵表示了一个有 5 个节点、7 条边的无向图。节点编号从 0 到 4，对应着矩阵的行和列。

我们可以使用二维数组来存储这个邻接矩阵：

matrix = [
    [0, 1, 0, 1, 0],
    [1, 0, 1, 1, 0],
    [0, 1, 0, 1, 1],
    [1, 1, 1, 0, 1],
    [0, 0, 1, 1, 0],
]

其中，matrix[i][j] 表示节点 i 和节点 j 之间是否有边相连。

## 广度优先搜索

广度优先搜索是一种迭代的遍历方法。具体来说，我们从起点开始，依次遍历与它相连的所有节点，然后再依次遍历与这些节点相连的所有未访问过的节点，一直重复下去，直到找到终点或者所有节点都被遍历过为止。

下面是使用广度优先搜索遍历上面那张图的 Python 代码：

from collections import deque

def bfs(matrix, start):
    n = len(matrix)
    visited = [False] * n  # 记录每个节点是否被访问过
    queue = deque()  # 用于记录待访问的节点
    queue.append(start)  # 将起点加入队列
    visited[start] = True  # 标记起点为已访问
    while queue:
        node = queue.popleft()  # 取出队首节点
        print(node, end=' ')  # 输出当前节点
        for i in range(n):
            if matrix[node][i] == 1 and not visited[i]:
                visited[i] = True  # 标记相邻节点为已访问
                queue.append(i)  # 将相邻节点加入队列

# 示例
matrix = [
    [0, 1, 0, 1, 0],
    [1, 0, 1, 1, 0],
    [0, 1, 0, 1, 1],
    [1, 1, 1, 0, 1],
    [0, 0, 1, 1, 0],
]
bfs(matrix, 0)  # 从节点 0 开始遍历

输出为：

0 1 3 2 4

在上面的代码中，我们使用了 Python 内置的 deque 类来实现队列。visited 数组用于记录每个节点是否被访问过。我们从起点开始，依次遍历与它相连的所有节点，将这些节点加入队列中。然后从队列中取出队首节点，依次遍历与它相连的所有未访问过的节点，将这些节点加入队列中。重复上述过程，直到队列为空为止。

希望上述解答能对你有所帮助！