Python实现BFS图遍历打印路径未覆盖全部节点问题排查

问题背景 #

需求为通过广度优先搜索（BFS）实现图结构遍历，打印遍历过程中的所有行进路径，要求生成的路径覆盖图中全部11个节点。
原有代码运行结果不完整，输出的最长路径仅包含6个节点，多数节点未出现在结果中，实际输出路径如下：

• [0, 2, 3, 1, 3]
• [0, 2, 4, 2]
• [0, 2, 3, 5, 3]
• [0, 2, 6, 7, 6]
• [0, 2, 3, 5, 9, 5]
• [0, 2, 4, 5, 10, 5]
• [0, 2, 3, 5, 9, 10]

原有问题代码 #

import copy
graph = {
  0 : [2],
  1 : [3],
  2 : [0,3,4,6],
  3 : [1,2,5],
  4 : [2,5,7],
  5 : [3,4,9,10],
  6 : [2,7,8],
  7 : [4,6,9],
  8 : [6,9],
  9 : [5,7,8,10],
  10 : [5,9]
}
visited = [] # 存储已访问节点
queue = []     # 初始化BFS队列
list = [[0]]
def bfs(visited, graph, node): # BFS函数
  visited.append(node)
  queue.append(node)

  while queue:          # 循环遍历队列节点
    m = queue.pop(0) 
    print (m, end = "-->")
    for neighbour in graph[m]:
        temp = []
        for raw in list:
            if raw[-1]==m :# 匹配路径末尾为当前节点的项
                    temp = copy.deepcopy(raw) 
                    raw.append(neighbour)# 给匹配到的路径追加邻居节点
                    break                # 匹配到第一个就终止循环
        
        if neighbour not in visited:
            visited.append(neighbour)
            queue.append(neighbour)
        if temp != '' :  # 保存旧路径用于生成新分支
            list.append(temp) 

# 执行入口
print("Following is the Breadth-First Search")
bfs(visited, graph, 0)
for i in list:       # 仅输出长度大于等于6的路径
  if len(i) >= 6:
    print(i)

核心错误点 #

原有代码无法覆盖全部节点的直接原因如下：

• 路径匹配提前终止：处理当前节点的邻居时，遍历路径列表找到第一个末尾等于当前节点的路径就直接break，其余所有终点为当前节点的合法路径都不会被扩展，直接丢失了大量分支。
• 路径扩展逻辑遗漏：仅给找到的第一条路径追加邻居节点，其余同终点的路径不会生成新的分支路径，后续节点自然无法被纳入路径结果。
• 类型判断错误：变量temp初始值是空列表[]，但判断条件写为temp != ''，空列表和空字符串类型不相等，该判断恒成立，会把无意义的空值塞入路径列表，污染结果。
• 原路径被篡改：扩展路径时直接修改原列表中存储的路径对象，没有保留原路径副本，后续分支扩展时用到的基准路径已经被之前的操作修改，路径生成完全混乱。
• 结果过滤不合理：最终输出时仅保留长度≥6的路径，遍历过程中生成的短路径被全部过滤，直观上看起来节点覆盖不全。

修正后实现 #

BFS记录路径的标准实现是直接在队列中存储「从起点到当前节点的完整路径」，出队时即可直接拿到对应路径，不需要单独维护全局路径列表，从根源避免路径分支丢失的问题。修正后代码如下：

from collections import deque

graph = {
    0: [2],
    1: [3],
    2: [0, 3, 4, 6],
    3: [1, 2, 5],
    4: [2, 5, 7],
    5: [3, 4, 9, 10],
    6: [2, 7, 8],
    7: [4, 6, 9],
    8: [6, 9],
    9: [5, 7, 8, 10],
    10: [5, 9]
}

def bfs_traverse(graph, start_node):
    visited = set()
    path_queue = deque()
    # 队列初始存入起点路径
    path_queue.append([start_node])
    visited.add(start_node)
    all_traverse_paths = []

    while path_queue:
        # 取出队首路径
        current_path = path_queue.popleft()
        current_node = current_path[-1]
        all_traverse_paths.append(current_path)
        # 遍历所有邻居生成新路径
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                new_path = current_path.copy()
                new_path.append(neighbor)
                path_queue.append(new_path)
    return all_traverse_paths, visited

# 执行遍历
print("广度优先搜索遍历节点顺序：")
paths, covered_nodes = bfs_traverse(graph, 0)
print(" --> ".join(str(path[-1]) for path in paths))

print("\n遍历生成的所有路径（按BFS层级排序）：")
for path in paths:
    print(path)

print(f"\n节点覆盖校验：共覆盖{len(covered_nodes)}个节点，节点列表为{sorted(covered_nodes)}")

运行修正后代码，遍历顺序为0 --> 2 --> 3 --> 4 --> 6 --> 1 --> 5 --> 7 --> 8 --> 9 --> 10，可完整覆盖图中全部11个节点，无遗漏。

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