迭代 DFS 与递归 DFS 以及不同的元素顺序

2021-12-24 00:00:00 depth-first-search algorithm graph traversal c++

我编写了一个递归 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);
            }
        }
    }

我的问题是，在一个图中，例如，我输入三个节点 'a', 'b', 'c' 与弧 ('a', 'b') 和 ('a', '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:

'a'、'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 children.

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

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

在递归方法中:当您看到每个节点时，您就对其进行处理.因此，您处理的第一个节点是第一个子节点.

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

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

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

相关文章