以连接矩阵为储存单位,采用广度优先遍历算法遍历图

连接矩阵是一种常见的图储存方式，它用一个二维数组来表示图中的节点之间的关系。如果节点 i 和节点 j 之间有连线，则连接矩阵中第 i 行第 j 列的元素为 1，否则为 0。

广度优先遍历算法是一种常见的图遍历算法，它从图的某个节点开始，依次访问其相邻节点，然后再依次访问这些相邻节点的相邻节点，直到遍历完整个图。

具体实现时，可以使用一个队列来存储待访问节点。首先将起始节点入队，然后每次从队列头取出一个节点，并将其所有未访问过的相邻节点入队。重复执行这个过程，直到队列为空。

利用连接矩阵来实现广度优先遍历算法，可以按照以下步骤进行：

1. 创建一个大小为 n 的队列，其中 n 是图中节点的数量。
2. 创建一个大小为 n 的布尔数组 visited，用来记录每个节点是否被访问过。
3. 将起始节点入队，并将 visited 数组中对应的元素设为 true。
4. 从队列头取出一个节点，遍历它的所有相邻节点。对于每个相邻节点，如果它还没有被访问过，就将它入队，并将 visited 数组中对应的元素设为 true。
5. 重复执行步骤 4，直到队列为空为止。

以下是一个使用连接矩阵实现广度优先遍历算法的示例代码：

def bfs(graph, start):
    n = len(graph)
    visited = [False] * n
    queue = [start]
    visited[start] = True
    while queue:
        node = queue.pop(0)
        print(node)
        for i in range(n):
            if graph[node][i] == 1 and not visited[i]:
                queue.append(i)
                visited[i] = True

其中 graph 是连接矩阵，start 是起始节点的索引。该函数会依次遍历图中所有与起始节点连通的节点。