algorithm - グラフ理論の深さ優先探索

Question

スタックを使用してDFSトラバーサルを実装しているときに、要素がすでにスタック内にあるがアクセスされていない場合は、要素をスタックにプッシュする必要がありますか？

Answer 1

要素が既にスタック内にあるがアクセスされていない場合、要素をスタックにプッシュする必要がありますか?

ループに入る 1 つの方法であるため、答えはノーです。

深さ優先検索を使用してグラフをトラバースしている場合、ループに陥る可能性があります。

この問題を回避する最善の方法は、訪問したすべてのノードの ID を保持するタブー リストを使用することです。

stack.push(init);

while (!stack.empty())
{
    current = stack.pop();
    taboo.add(current.id);

    if (isGoal(current))
    {
        break;
    }

    for (Node neighbor : getNeighbors(current))
    {
        if (!taboo.contains(neighbor.id))
        {
            stack.push(neighbor);
        }
    }

}