如何基于顶点列表与邻接矩阵正确实现BFS算法

现有一份基于邻接表字典实现的BFS算法参考代码，其图结构以字典形式存储顶点与邻接点的映射关系。需要处理的图由两个独立列表构成：

• 其一为顶点列表
• 其二为邻接矩阵：矩阵中对应位置值为1代表两个位置的顶点间存在连边，值为0代表两顶点无连接、或为同一顶点（不存在自环）。

参考邻接表版本BFS编写适配双列表结构的代码时出现异常：尽管使用Q.pop(0)尝试在每次迭代时移除队首元素，队列Q的元素始终未按预期移除，无法完成正确的BFS遍历，需要将参考算法适配到当前的双列表结构中。

graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

visited = [] # 存储已访问节点
queue = []     # 初始化队列

def bfs(visited, graph, node):
  visited.append(node)
  queue.append(node)

  while queue:
    s = queue.pop(0) 
    print (s, end = " ") 

    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# 驱动代码
bfs(visited, graph, 'A')

V = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
M = [0,1,0,0,0,0,0],[1,0,1,1,0,0,0],[0,1,0,1,0,0,0],[0,1,1,0,1,0,0],[0,0,0,1,0,1,0],[0,0,0,0,1,0,1],[0,0,0,0,0,1,0]
Q = []
visited = []
E = []

def BFS(V,M): 

    Q.append('A')
    visited.append('A')

    while Q: 
        s = Q.pop(0) 
        

    for a,b in enumerate(M): 
        for i,j in enumerate(b): 
            if j == 1 and V[i] not in visited: 
            
                Q.append(V[i]) 
                visited.append(V[i])
                
            if b.count(1) > 2 and V[i] != V[i]: 
                E.append(V[i])
                Q.extend(E)
        print(Q) 
         
            
                 
                        
  
print(BFS(V,M))

原有代码核心问题 #

• 缩进错误：遍历邻接矩阵查找邻居的逻辑全部写在while Q循环外部，while循环仅反复执行出队操作直到队列为空，完全不符合BFS「出队当前节点→查找当前节点邻居→将未访问邻居入队」的执行顺序。
• 邻接矩阵匹配逻辑错误：查找邻居时没有和当前出队的节点绑定，直接遍历了整个邻接矩阵的所有边，没有先定位当前节点对应的邻接矩阵行。
• 无效冗余逻辑：判断条件V[i] != V[i]恒为假，对应的E列表相关代码没有任何实际作用，属于冗余内容。
• 变量作用域问题：队列、已访问列表定义为全局变量，多次调用函数会残留历史运行数据，导致结果异常。

修复后可运行代码 #

V = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
M = (
    [0,1,0,0,0,0,0],
    [1,0,1,1,0,0,0],
    [0,1,0,1,0,0,0],
    [0,1,1,0,1,0,0],
    [0,0,0,1,0,1,0],
    [0,0,0,0,1,0,1],
    [0,0,0,0,0,1,0]
)

def BFS(vertex_list, adj_matrix, start_node):
    visited = []
    queue = []
    # 初始化：起点入队、标记已访问
    visited.append(start_node)
    queue.append(start_node)

    while queue:
        # 出队队首节点
        current_node = queue.pop(0)
        print(current_node, end=" ")
        # 找到当前节点在顶点列表中的索引
        current_idx = vertex_list.index(current_node)
        # 遍历当前节点对应的邻接矩阵行，找所有邻居
        for neighbor_idx, is_connected in enumerate(adj_matrix[current_idx]):
            neighbor = vertex_list[neighbor_idx]
            # 有连边且未访问过，就标记并入队
            if is_connected == 1 and neighbor not in visited:
                visited.append(neighbor)
                queue.append(neighbor)
    return visited

# 驱动测试
print("\nBFS遍历结果：")
BFS(V, M, 'A')

运行输出 #

BFS遍历结果：
A B C D E F G 

优化提示：如果顶点数量较多，建议使用collections.deque作为队列结构，用popleft()方法替代pop(0)，可以将队首出队的时间复杂度从O(n)降到O(1)，提升遍历效率。

内容的提问来源于stack exchange，提问作者MrTiredVeryTired