このpythonパス検索で正しいパスが見つかるようにするにはどうすればよいですか？

Question

def rightMostPath(graph, root, target, path = None): 
    if path == None: 
     path = [] 
    path.append(root) 
    if root == target: 
     return path 
    if root not in graph.keys(): 
     return None 
    for v in graph[root]: 
     if v not in path: 
      ep = rightMostPath(graph, v, target, path) 
      if ep: 
       return ep 
    return None 

if __name__ == '__main__': 
    graph = {0: [1], 1: [0, 2, 3], 2: [1], 3: [1]} 
    R = rightMostPath(graph, 0, 3) 
    print(R) 

この単純なグラフを描いた後、経路が[0,1,3]であることが明らかな場合、上記のコードは答えが[0,1,2,3]として返されます。私は、これが起こる原因を知りたかったのは、Pythonでグラフ構造のこのタイプのパス検索を指し示す場所を指していたからです。

Answer 1

主な問題は、それが動作します知っている前に、あなたが解決策にルートパスを追加していることです。失敗した場合は削除しないでください。 のパスがどこにでも渡されているので、それは更新しているマスターコピーです。失敗したノードはまだパスにあります。あなたが訪問したすべてのノードは、それがソリューションに貢献してもいなくても、最終コピーに表示されます。

いずれに失敗した場合にパスからルートを削除するか、あなたは（あなたのロジックで他のいくつかの変更を必要とする）が正常に戻るまで、それを追加しないでください。

クイックソリューション：ちょうどあなたがなしを返さない各スポットの前にライン

path.remove(root) 

を追加します。私は今、そのケースの予想される出力を得て、論理的な流れはこれらの老化の目にDFSのように見えます。

def rightMostPath(graph, root, target, path = None): 
    if path == None: 
     path = [] 
    path.append(root) 
    if root == target: 
     return path 
    if root not in graph.keys(): 
     path.remove(root) # Restore path 
     return None 
    for v in graph[root]: 
     if v not in path: 
      ep = rightMostPath(graph, v, target, path) 
      if ep: 
       return ep 

    path.remove(root) # Restore path 
    return None