如何使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,2,3]，当绘制完这个简单的图形后，很明显路径应该是[0,1,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