迭代DFS与递归DFS和不同元素顺序

Question

我编写了一个递归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')我的输出是:

带有递归DFS版本的'a','b','c',以及:

带有迭代DFS的'a','c','b'.

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

谢谢!

Answer 1

两者都是有效的 DFS算法.DFS不会指定您首先看到的节点.这并不重要,因为边缘之间的顺序没有定义[记住:边缘通常是一组].不同之处在于您处理每个节点的子节点的方式.

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

在递归方法中:您在看到每个节点时处理它们.因此,您处理的第一个节点是第一个孩子.

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