在 Python 中递归地使用父数组查找路径

Question

所以我有一个任务，就是写一个函数，把遍历产生的parents数组，起始顶点，结束顶点，产生一条从起始顶点到结束顶点的路径。

我试过为此编写代码

def tree_path(parents, start, end):
    if ((start == end) or (end == -1)):
        return [start, end]
    else:
        return tree_path(parents, start, parents[end])

它没有按照我的预期去做。我不太擅长递归。任何帮助将非常感激。谢谢

Answer 1

你可以试试，假设我们想要一个从start到end的所有顶点的列表，如下：

def tree_path(parents, start, end):
    if (start == end) or (end == -1):
        return [start]
    else:
        return tree_path(parents, start, parents[end]) + [end]

如果start与end重合，那么我们的路径只包含一个顶点：start。否则，我们找到从 start 到 end 的父节点的路径，并向该路径添加 end 节点。

Answer 2

你一直递归直到 start==end，然后 return [start,end]。那总是 [start,start]（因为 start==end），所以你什么也学不到。您只需要在第一个 return 语句中 return [start]，因为 returning [start,end] 将 return 具有相同元素的列表两次。另一个 return 语句也需要添加一些东西；否则，您将只有 return 两个元素：return tree_path(parents, start, parents[end]) + [end]

不过这也有问题（我想）。 parents[end] 是（我认为）parents 的列表。不过，tree_path() 只需要一个端节点。您需要遍历它们以查看哪个有效（如果我认为它是列表是错误的，请忽略这部分并使用上面的代码）：

for i in parents[end]:
    path = tree_path(parents,start,i):
    if path:
        return path + [end]

这假定 tree_path() return 在找不到路径时为假值。您需要检查 end 是否为根节点。我假设这就是 end==-1 检查的作用。把它们放在一起，你会得到这样的东西：

def tree_path(parents, start, end):
    if end==-1:
        return None
    if start==end:
        return [end]
    else:
        for i in parents[end]:
            path = tree_path(parents,start,i):
            if path:
                return path + [end]

在 Python 中递归地使用父数组查找路径

Finding a path using the Parents Array Recursively in Python

python

recursion

path-finding