图的广度优先遍历基于邻接矩阵 python实现

以下是基于邻接矩阵的图的广度优先遍历的 Python 实现：

from queue import Queue

# 定义邻接矩阵
graph = [[0, 1, 1, 0],
         [1, 0, 1, 1],
         [1, 1, 0, 1],
         [0, 1, 1, 0]]

# 定义起始节点
start_node = 0

# 定义 BFS 函数
def bfs(graph, start):
    # 创建一个队列并将起始节点入队
    queue = Queue()
    queue.put(start)
    
    # 定义 visited 数组记录已经访问过的节点
    visited = [False] * len(graph)
    visited[start] = True
    
    # 从队列中取出元素，并访问其邻居节点
    while not queue.empty():
        node = queue.get()
        print(node)
        for neighbor in range(len(graph[node])):
            if graph[node][neighbor] == 1 and not visited[neighbor]:
                queue.put(neighbor)
                visited[neighbor] = True

# 调用 BFS 函数
bfs(graph, start_node)

运行结果：

0
1
2
3

这里的邻接矩阵 `graph` 表示有 4 个节点的无向图，其中 `graph[i][j]` 表示节点 i 和节点 j 之间是否有边。前面的 BFS 函数基于队列实现，每次取出队列头的元素，并访问它的邻居节点，直到队列为空。为了避免重复访问同一个节点，我们使用 `visited` 数组记录已经访问过的节点。