python - 图中的回溯

Question

在 python 中，我有一个图作为邻接列表演示。 以及从特定点到图中所有其他元素的距离。

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

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

如何从元素回溯路径: 例如，如果我尝试从 10 回溯，它应该返回:

[10, 7, 1, 2]
[10, 7, 8, 3]
[10, 6, 8, 3]

我尝试递归地执行此操作

def findprev(graph, distance, el, path = []):
    value = distance[el]
    if value == 0:
        print path
        path = []

    for i in graph[el]:
        if value - 1 == distance[i]:
            path.append(i)
            path = findprev(graph, distance, i, path)
    return path

但显然我失去了一些重要的东西，因为结果是:

[7, 1, 2]
[8, 3]
[6, 8, 3]

任何人都可以帮忙找到错误吗

Answer 1

def findprev(graph, distance, el, path=None):
    if path is None:
        path = [el]
    else:
        path.append(el)
    value = distance[el]
    if value == 0:
        print(path)

    for i in graph[el]:
        if value - 1 == distance[i]:
            findprev(graph, distance, i, path[:])

findprev(graph, distance, 10)

输出:

[10, 7, 1, 2]
[10, 7, 8, 3]
[10, 6, 8, 3]

或者，如果您想返回结果路径:

def findprev(graph, distance, el, path=None):
    if path is None:
        path = [el]
    else:
        path.append(el)
    value = distance[el]
    if value == 0:
        return [path]

    result = []
    for i in graph[el]:
        if value - 1 == distance[i]:
            paths = findprev(graph, distance, i, path[:])
            for p in paths:
                result.append(p)
    return result