在圖中回溯

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] 

誰能幫助找到一個bug

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 

Answer 2

這裏是另一個解決方案你的問題。我將distance更名爲distances，因爲它對我來說似乎是一個更好的名稱，我用每個點的距離名稱distance。

>>> def find_paths(point,path=[]): 
     distance = distances[point] 
     elements = graph[point] 
     if distance == 0: 
      yield path + [point] 
     else: 
      for element in elements: 
       if distances[element] == distance - 1: 
        for item in find_paths(element,path+[point]): 
         yield item 


>>> for path in find_paths(10): 
     print path 


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