Python 邻接矩阵 广度优先搜索

邻接矩阵是一种表示图的数据结构，可以用它来存储图中的节点和边。在邻接矩阵中，每个节点与其他节点之间的关系用一个矩阵来表示，矩阵中的每个元素表示两个节点之间是否有边相连。

广度优先搜索（BFS）是一种图遍历算法，从指定的起始节点开始，依次访问与其相邻的节点，直到遍历完所有节点。BFS的遍历方式类似于层次遍历，先访问起始节点，然后访问所有与其相邻的节点，再访问这些节点的相邻节点，依此类推。

下面是 Python 中邻接矩阵的实现：

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, i, j):
        self.adj_matrix[i][j] = 1
        self.adj_matrix[j][i] = 1

    def bfs(self, start_vertex):
        visited = [False] * self.num_vertices
        queue = []
        queue.append(start_vertex)
        visited[start_vertex] = True

        while queue:
            current_vertex = queue.pop(0)
            print(current_vertex, end=' ')

            for i in range(self.num_vertices):
                if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
                    queue.append(i)
                    visited[i] = True

上面的代码中，Graph 类中的 adj_matrix 用于存储邻接矩阵，add_edge 方法用于添加边，bfs 方法用于实现广度优先搜索。

在 bfs 方法中，visited 用于记录每个节点是否被访问过，queue 用于存储待访问的节点。首先将起始节点加入队列，并将其标记为已访问。然后，如果队列不为空，就取出队列中的第一个节点，打印它，并将它的相邻节点加入队列。最后，将已访问的节点标记为 True。重复执行以上步骤，直到队列为空，搜索结束。

下面是一个示例：

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(2, 4)
g.bfs(0)

输出：

0 1 2 3 4

这个示例中，起始节点是 0，我们按照广度优先的顺序遍历了整个图。