BFS所有特定深度的路径

Question

我正在使用NetworkX库来生成一个无方向的图形，给定父母的关系。给定的深度x和图形的起点，我可以在深度x上找到所有节点，但是我也希望所需的路径到达该节点。到达路径时，我如何收集遍历的节点？

这是我的代码，它可以在depth＆lt＆= 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

为我提供所有节点。 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和decort = 3输出应为 {1：{2，3，4}，2：{8，9，6，7}，3：{10}}}其中key = gandy = distance and 值=距离处的节点。

我想要的是每个键值对穿过的节点。例如，在depth = 2节点为{8,9,6,7}（顺序没关系），每个节点都像这样。 。 1-4-8，1-3-9，1-2-6，1-4-7

让我知道是否需要进一步澄清。

Answer 1

这样的事情可能会起作用：我添加了另一个词典，该字典在途中收集了每个站点，而Ouput与您所说的相同
（请参阅底部输出）

...
    ...
    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]}}