4

そこで、最近、非再帰バージョンの DFS を実装しました。ノードがスタックにプッシュされるとすぐに、またはポップアウトされるとすぐに、ノードを「訪問済み」とマークできることがわかりました。私が取り組んでいた問題は、スタックにプッシュされたときに「訪問済み」とマークするように具体的に述べられていました。どちらのバージョンもある種の DFS です。それとも、一方が DFS で、もう一方がそうでないようなものですか。どんな提案も歓迎します。

私が思うのは、2 番目の方法を実行すると、再帰的な dfs を模倣するということです。しかし、なぜもう一方は機能するのでしょうか。

再帰的な dfs (これは無視してください)

dfsRec(node)
{
    visitedArray[node]=1;

    for all neighbours of node
        if they aren't visited
            dfsRec(neighbour);
}

dfs(startNode)
{
    visitedArray;
    dfsRec(startNode);  
}
4

1 に答える 1

3

2 番目の方法 (つまり、ノードがポップアウトされたときにアクセスしたノードをマークする) の問題は、グラフにサイクルがあるたびに、コードが永久にループすることです。DFS がそのサイクルに達すると、ノードはスタックからポップされるまで訪問済みとしてマークされないため、円を描き続けます。そのため、サイクルを通じて到達可能なノードは、メモリがなくなるまで何度もプッシュされます。

この問題は、DFS の再帰的な実装とあまり変わらないことに注意してください。再帰的な実装では、メモリ不足ではなくスタック オーバーフローが発生しますが、その理由は同じです。

于 2013-11-03T20:13:00.953 に答える