1

スタックを使用してパスを返したいのですが、不可能だと思います。

ノードは、その背後にあるパスを受信できるように、親から直接呼び出される必要がありますが、このノードがスタックにプッシュされると、これまでのところパスが失われます。スタックを使用すると、ノードが個別に評価され、ノードの親へのパスをノードに渡すことができませんでした。

宿題なので、ノードにパスのプロパティを持たせることはできません。

私はこれに一週間以上困惑しています！

4

2 に答える 2

0

スタックからノードをポップするときはいつでも、そのノードにつながるパスを取得する方法が必要です。

(node, path)1つの解決策は、値だけでなく、スタック上のタプルをプッシュするnodeことです。Haskellのような純粋関数型リストの場合path、これは良い解決策ですが、Pythonでは慣用的ではない可能性があります。また、厳密に言えばパスはノード内に格納されていませんが、このソリューションはおそらく質問の精神に含まれていません。

別の解決策は、以前にアクセスしたノードへのパスを含む別のスタックを維持することです。深さ優先スタックには、検索でのノードの深さが(node, depth)どこにあるかのタプルが含まれています。depthパスの最後に追加nodeする前に、パスの長さがに等しくなるまで要素がパスからポップされますdepth。

于 2011-09-13T10:29:18.343 に答える
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 に答える