使用栈的深度优先搜索能返回到达目标的路径吗？

Question

我想用栈来返回一条路径，但我觉得这可能行不通。

一个节点必须由它的父节点直接调用，这样它才能接收到它后面的路径。而当这个节点被放入栈中时，它就失去了之前的路径。使用栈的话，节点就会孤立地被评估，我无法把路径传递给这个节点的父节点。

我不能让节点拥有它后面的路径这个属性，因为这是一个作业。

我在这个问题上卡了超过一周了！

Answer 1

"一个节点必须由它的父节点直接调用，这样它才能接收到它后面的路径，" <- 这听起来没问题。

而当这个节点被放到栈里时，它就失去了到目前为止的路径。 <- 我认为这并不需要担心。

你可以做的是用类似的方法递归地构建栈，

def makepath(someGraph, from, to):
    if(from == to)
        return ""

    nextNode= <...> #find out next node in path here
    return makepath(someGraph, nextNode, to) + str(nextNode)

Answer 2

每当你从栈中取出一个节点时，你需要一种方法来获取到达这个节点的路径。

一种解决办法是将节点和路径一起放入栈中，也就是把它们作为一个元组 (node, path) 压入栈，而不是单独放入 node 的值。如果 path 是像 Haskell 那样的纯函数列表，这个方法是不错的，但在 Python 中可能不太符合习惯。而且，虽然严格来说路径并没有存储在节点内部，但这个方法可能不太符合问题的本意。

另一种解决办法是维护一个单独的栈，用来存放到达之前访问过的节点的路径。深度优先搜索的栈中包含 (node, depth) 的元组，其中 depth 是节点在搜索中的深度。在将 node 添加到路径的末尾之前，会从路径中弹出一些元素，直到路径的长度等于 depth。