给定父节点而非子节点关系时如何用Python实现广度优先搜索

问题背景 #

用Python字典存储图结构时，常规广度优先搜索（BFS）依赖子节点映射关系：字典的键是节点，值是该节点所有直接子节点的列表，示例结构如下：

# 子节点映射结构
graph_child = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

当前场景下拿到的是父节点映射关系：字典的键是节点，值是该节点所有直接父节点的列表，示例结构如下：

# 父节点映射结构
graph_parent = {
  'A' : [],
  'B' : ['A'],
  'C' : ['A'],
  'D' : ['B'],
  'E' : ['B'],
  'F' : ['C','E']
}

实现方法 #

两种方案都可以实现，根据你的场景选即可：

方案1：预处理反转字典，复用标准BFS逻辑 #

这是通用性最高的方案，先把父节点映射反转成常规的子节点映射，之后直接用你熟悉的标准BFS逻辑即可，不需要改动原有遍历代码，遍历效率高，适合节点量大、需要多次遍历的场景：

from collections import deque

def bfs_with_parent_map(parent_graph, start_node):
    # 反转父节点映射，构造子节点映射
    child_graph = {node: [] for node in parent_graph}
    for node, parent_list in parent_graph.items():
        for parent in parent_list:
            child_graph[parent].append(node)
    
    # 标准BFS流程
    visited = set()
    traversal_result = []
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        cur_node = queue.popleft()
        traversal_result.append(cur_node)
        for child in child_graph[cur_node]:
            if child not in visited:
                visited.add(child)
                queue.append(child)
    return traversal_result

# 测试：从根节点A出发遍历
print(bfs_with_parent_map(graph_parent, 'A'))
# 输出结果：['A', 'B', 'C', 'D', 'E', 'F']

方案2：不做预处理，遍历时动态查找子节点 #

如果图的节点数不多、不需要多次遍历，可以不用额外存储反转后的子节点映射，每次处理当前节点时，直接遍历全图找到所有把当前节点作为父节点的节点，就是当前节点的直接子节点，代码更简洁：

from collections import deque

def bfs_direct(parent_graph, start_node):
    visited = set()
    traversal_result = []
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        cur_node = queue.popleft()
        traversal_result.append(cur_node)
        # 动态查找当前节点的所有直接子节点
        for node, parent_list in parent_graph.items():
            if cur_node in parent_list and node not in visited:
                visited.add(node)
                queue.append(node)
    return traversal_result

注意：如果你的图不是有向无环图、存在环路，必须加visited集合标记已访问节点，否则会出现死循环。

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