我写了一个递归算法DFS遍历一个图：

I have written a recursive DFS algorithm to traverse a graph:

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算法：

Then I have written an iterative DFS algorithm using a stack:

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

我的问题是，在一个曲线图，其中，例如，我进入三个节点'一'，'B'，'C'与弧（A，B）和（'一个'，' C'）我的输出是：

My problem is that in a graph in which, for example, I enter the three nodes 'a', 'b', 'c' with arcs ('a', 'b') and ('a', 'c') my output is:

一，B，C与递归DFS版本，和

'a', 'b', 'c' with the recursive DFS version, and:

A，C，B与迭代DFS之一。

'a', 'c', 'b' with the iterative DFS one.

我怎么能得到同样的顺序？难道我做错了什么？

How could I get the same order? Am I doing something wrong?

感谢您！

推荐答案

两者都是有效的 DFS算法。一个DFS没有规定你先看看哪个节点。这并不重要，因为边缘之间的顺序没有定义[记住：边缘是一组通常]。所不同的是，由于你处理每一个节点的两个儿子的方式。

Both are valid DFS algorithms. A DFS does not specify which node you see first. It is not important because the order between edges is not defined [remember: edges are a set usually]. The difference is due to the way you handle each node's sons.

在迭代的方法：你先插入的所有元素进栈 - 那么昂处理堆栈的头[这是最后一个节点插入] - 这样的第一个节点，你手柄是最后一个儿子

In the iterative approach: You first insert all the elements into the stack - ang then handle the head of the stack [which is the last node inserted] - thus the first node you handle is the last son.

在递归方法：当您看到它处理每一个节点。因此，你处理的第一个节点是第一个儿子

In the recursive approach: You handle each node when you see it. Thus the first node you handle is the first son.

要进行反复的DFS产生相同的结果递归一 - 你需要的在相反的顺序添加元素堆栈 [为每个节点，首先将其最后儿子和它的第一个儿子最后]

To make the iterative DFS yield the same result as the recursive one - you need to add elements to the stack at reverse order [for each node, insert its last son first and its first son last]