NetworkX中BFS遍历获取指定深度节点及对应路径方法

问题背景 #

使用networkx库构建无向图时，基于层序遍历（BFS）已经可以实现获取距离源点指定深度范围内的所有分层节点，需要在此基础上额外收集从源点到每个节点的完整遍历路径。
现有可正常运行的分层节点获取代码如下：

import networkx as nx

def descendants_at_distance(G, source, distance):
    if not G.has_node(source):
        raise nx.NetworkXError(f"The node {source} is not in the graph.")
    current_distance = 0
    current_layer = {source}
    visited = {source}
    layer_with_distance = {}

    while current_distance < distance:
        next_layer = set()
        for node in current_layer:
            for child in G[node]:
                if child not in visited:
                    visited.add(child)
                    next_layer.add(child)
        current_layer = next_layer
        current_distance += 1
        layer_with_distance.update({current_distance: current_layer})
    
    layer_with_distance =  {key:val for (key, val) in layer_with_distance.items() if val}
    return layer_with_distance

测试用图构建代码：

df_links = [(1,2),(1,3),(1,4),(2,6),(3,9),(4,7),(4,8),(9,7),(9,10),(7,8),(7,10), (15,16)]
Graph = nx.Graph(df_links)

当入参为source=1、distance=3时，现有代码输出为{1: {2, 3, 4}, 2: {8, 9, 6, 7}, 3: {10}}，键为节点到源点的距离，值为对应距离下的节点集合。
预期新增输出为每个节点对应的从源点出发的遍历路径，例如深度2的节点8对应路径1-4-8、节点9对应路径1-3-9。

实现方法 #

核心逻辑是在BFS遍历过程中维护前驱节点映射表，记录每个节点第一次被访问时的上游节点，遍历结束后通过前驱表回溯即可生成从源点到任意节点的完整路径，该方案完全兼容原有层序遍历逻辑，不会改变原有分层结果。
修改后的完整代码如下：

def descendants_at_distance_with_path(G, source, distance):
    if not G.has_node(source):
        raise nx.NetworkXError(f"The node {source} is not in the graph.")
    current_distance = 0
    current_layer = {source}
    visited = {source}
    layer_with_distance = {}
    # 维护前驱映射：key为当前节点，value为BFS遍历中访问该节点的上一级节点
    predecessor = {source: None}

    while current_distance < distance:
        next_layer = set()
        for node in current_layer:
            for neighbor in G[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    next_layer.add(neighbor)
                    predecessor[neighbor] = node
        current_layer = next_layer
        current_distance += 1
        if current_layer:
            layer_with_distance[current_distance] = current_layer
    
    # 从前驱映射回溯生成指定节点的完整路径
    def build_path(target):
        path = []
        cur = target
        while cur is not None:
            path.append(cur)
            cur = predecessor[cur]
        # 反转后得到源点到目标点的正序路径
        return path[::-1]
    
    # 构建所有节点的路径映射
    node_path_map = {}
    for dist, nodes in layer_with_distance.items():
        for n in nodes:
            node_path_map[n] = build_path(n)
    
    return layer_with_distance, node_path_map

调用示例 #

layers, path_map = descendants_at_distance_with_path(Graph, source=1, distance=3)

返回值说明：

• layers：和原有函数输出完全一致的分层节点字典
• path_map：节点到路径的映射字典，key为节点id，value为从源点到该节点的路径列表

测试输出：

• 分层结果：{1: {2, 3, 4}, 2: {6, 7, 8, 9}, 3: {10}}
• 路径映射：
  • 节点2：[1,2]
  • 节点3：[1,3]
  • 节点4：[1,4]
  • 节点6：[1,2,6]
  • 节点7：[1,4,7]
  • 节点8：[1,4,8]
  • 节点9：[1,3,9]
  • 节点10：[1,3,9,10]

注意事项 #

• 无向图BFS第一次访问节点时得到的路径即为两节点间的最短路径，和层序遍历的深度定义完全匹配
• 路径生成逻辑不会额外增加遍历复杂度，整体时间复杂度和原有BFS逻辑一致，均为O(V+E)
• 如果需要格式化路径为1-4-8的字符串形式，直接用'-'.join(map(str, path))转换即可

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