我该如何做到这一点，以便此Python Path搜索找到正确的路径

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

主要问题是将 root 附加到解决方案 PATH 之前，然后才能不起作用；如果失败，则不会删除它。由于 PATH 到处都在各处传递，这就是您要更新的主副本 - 失败的节点仍在路径中。您访问的每个节点（无论是否有助于解决方案）都出现在您的最终副本中。

从 PATH上删除 root 在失败时，或者在成功返回之前不要添加它（这需要逻辑上的其他一些更改）。

快速解决方案：添加行

path.remove(root)

在您返回无的每个位置之前。我现在得到了这种情况的预期输出，逻辑流看起来像是这些老化眼睛的DF。

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