BFS 所有路径到特定深度

Question

我正在使用 networkx 库生成一个给定父子关系的无向图。给定深度 x 和图形的起点，我可以找到深度 x 处的所有节点，但我还想要到达该节点的路径。如何收集到达路径时遍历的节点？[=24=]

这是我的代码，它让我获得 depth <= x

的所有节点

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:
            # print(G[node])
            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

以上代码是对内置networkx库代码的修改，因为我需要depth = 1...x

之间的所有节点

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}} 其中 key = distance 和 value = nodes at distance.

我想要的是在每个键值对处遍历的节点。比如depth = 2处的节点是{8,9,6,7}（顺序无所谓），每个遍历的节点是这样的。 1-4-8, 1-3-9, 1-2-6, 1-4-7

如果需要进一步说明，请告诉我。

Answer 1

这样的事情可能会奏效：我添加了另一个字典来收集沿途的每个站点，输出与您所说的相同（输出见底部）

...
    ...
    layer_with_distance = {}
    tracker = {} # added this
    while current_distance < distance:
        tracker[source] = {} # added this
        next_layer = set()
        for node in current_layer:
            # print(G[node])
            tracker[source][node] = []  # added this
            for child in G[node]:
                if child not in visited:
                    tracker[source][node].append(child) #added this
                    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, tracker # added to this


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)
print(descendants_at_distance(Graph, 1, 2))

输出

layer_with_distance: {1: {2, 3, 4}, 2: {8, 9, 6, 7}}

tracker: {1: {2: [6], 3: [9], 4: [7, 8]}}

BFS 所有路径到特定深度

BFS all paths to specific depth

python

python-3.x

networkx

breadth-first-search