1

我想使用堆栈并返回路径，但我认为这是不可能的。

一个节点必须由它的父节点直接调用，这样它才能接收到它后面的路径，而当这个节点被压入堆栈时，它会丢失到目前为止的路径。使用堆栈会导致一个节点被孤立地评估，并且我无法将节点的父节点的路径传递给节点。

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

我已经被这个难住了一个多星期！

4

2 回答 2

0

" A node must be called directly by its parent so that it can receive the path behind it," <- 这似乎没问题。

whereas when this node is pushed onto a stack, it loses the path so far.<- 我相信这没什么好担心的。

您可以做的是使用类似的东西递归地构建堆栈

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

    nextNode= <...> #find out next node in path here
    return makepath(someGraph, nextNode, to) + str(nextNode)
于 2011-09-13T04:50:30.623 回答
0

每当您从堆栈中弹出一个节点时，您都​​需要一种方法来检索通向该节点的路径。

一种解决方案是将 的元组推送到(node, path)堆栈上，而不仅仅是node值。如果path是像 Haskell 中的纯函数列表，这是一个很好的解决方案，但在 Python 中它可能不是惯用的。此外，虽然严格来说路径没有存储在节点中，但这个解决方案可能不符合问题的精神。

另一种解决方案是维护一个单独的堆栈，其中包含到先前访问的节点的路径。深度优先堆栈包含搜索中节点深度的元(node, depth)组depth。在添加node到路径的末尾之前，从路径中弹出元素，直到路径的长度等于depth。

于 2011-09-13T10:29:18.343 回答