[解決済み] 反復的DFSと再帰的DFSの比較と要素の順序の違い

質問

グラフを走査する再帰的DFSアルゴリズムを書きました。

void Graph<E, N>::DFS(Node n)
{
    std::cout << ReadNode(n) << " ";

    MarkVisited(n);

    NodeList adjnodes = Adjacent(n);

    NodeList::position pos = adjnodes.FirstPosition();

    while(!adjnodes.End(pos))
    {
        Node adj = adjnodes.ReadList(pos);

        if(!IsMarked(adj))
            DFS(adj);

        pos = adjnodes.NextPosition(pos);
    }
}

そして、スタックを使った反復型DFSアルゴリズムを書きました。

template <typename E, typename N>
void Graph<E, N>::IterativeDFS(Node n)
{
    Stack<Node> stack;

    stack.Push(n);

    while(!stack.IsEmpty())
    {
        Node u = stack.Read();

        stack.Pop();

        if(!IsMarked(u))
        {
            std::cout << ReadNode(u) << " ";

            MarkVisited(u);

            NodeList adjnodes = Adjacent(u);

            NodeList::position pos = adjnodes.FirstPosition();

            while(!adjnodes.End(pos))
            {
                stack.Push(adjnodes.ReadList(pos));

                pos = adjnodes.NextPosition(pos);
            }
        }
    }

私の問題は、例えば、3つのノード 'a', 'b', 'c' とアーク ('a', 'b') と ('a', 'c') を入力したグラフで、私の出力は次のようになります。

'a', 'b', 'c'を再帰的DFS版で、と。

a'、'c'、'b' は反復 DFS の方です。

どうしたら同じ順番になるのでしょうか？私のやり方が悪いのでしょうか？

ありがとうございました。

解決方法は？

どちらも有効 DFSのアルゴリズム。DFSは、どのノードが最初に見えるかを指定しない。エッジ間の順序は定義されないので、重要ではありません[エッジは通常集合であることを思い出してください]。違いは、各ノードの子をどのように扱うかによるものです。

では 繰り返しアプローチです。まず、すべての要素を挿入します。 をスタックに挿入し、次にスタックの先頭（最後に挿入されたノード）を処理します。 最初に処理するノードは、最後の子ノード .

で 再帰的アプローチ : 各ノードを見たときにそれを処理するのです。したがって 最初に扱うノードは、最初の子 .

反復型DFSが再帰型DFSと同じ結果になるようにするには、次のようにする必要があります。 スタックに逆順に要素を追加する [各ノードについて、その最後の子を最初に、その最初の子を最後に挿入する] 。