迭代 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);
            }
        }
    }

我的问题是，在一个图中，例如，我输入三个节点“a”，“b”，“c”，带有弧（“a”，“b”）和（“a”，“c”）我的输出是：

'a'、'b'、'c' 具有递归 DFS 版本，并且：

'a'、'c'、'b' 与迭代 DFS 之一。

我怎样才能得到同样的订单？难道我做错了什么？

谢谢你！

两者均有效DFS 算法。 DFS 并不指定您首先看到哪个节点。这并不重要，因为边之间的顺序没有定义[记住：边通常是一个集合]。差异是由于处理每个节点的子节点的方式造成的。

In the 迭代方法：首先插入所有元素进入堆栈 - 然后处理堆栈的头部[这是最后插入的节点] - 因此您处理的第一个节点是最后一个子节点.

In the 递归方法：当你看到每个节点时，你就可以处理它。就这样您处理的第一个节点是第一个子节点.

为了使迭代 DFS 产生与递归 DFS 相同的结果 - 你需要按相反顺序向堆栈添加元素[对于每个节点，首先插入其最后一个子节点，最后插入其第一个子节点]