c++ - 迭代 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') 我的输出是:

'a'、'b'、'c' 与递归 DFS 版本，以及:

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

我怎样才能得到相同的订单？我做错了吗？

谢谢!

Answer 1

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

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

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

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