迭代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算法。DFS不指定您首先看到的节点。这并不重要，因为边之间的顺序没有定义，记住:边通常是一个集合。不同之处在于处理每个节点的子节点的方式。

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

在递归方法中，：您可以在看到每个节点时对其进行处理。因此，您处理的第一个节点是第一个子。

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

Answer 2

在这里，我将递归地离开我的解决方案，以非常快的速度实现。对于任何需要使用此算法的问题，只需调整它即可。

将当前状态标记为已访问(定义为ok[u] = true )是非常重要的，即使将所有状态标记为未使用memset(ok, 0, sizeof ok)访问的状态也是如此

#define forn(i , a , b) for(int i=(a);i<(b);i++)

vector<int> arr[10001];
bool ok[10001];

void addE(int u , int v){
  arr[u].push_back(v);
  arr[v].push_back(u);
}

void dfs(int u){
  ok[u] = true;
  forn(v , 0 , (int)arr[u].size()) if(!ok[arr[u][v]]) dfs(arr[u][v]);
}

int main(){
  //...
  memset(ok , 0 , sizeof ok);
  //... 
  return 0;
}

Answer 3

最明显的区别是使用子对象的顺序。

在递归方法中:获取第一个子级，并在它出现时立即运行

在迭代方法中:你推入堆栈中的所有子节点，然后取堆栈的顶部，即最后一个子节点

要产生相同的结果，只需按相反的顺序插入子项即可。

另一个区别是内存使用，因为一个使用调用堆栈，而另一个使用您创建的堆栈或一个STL元素：

你可以在这里阅读到：https://codeforces.com/blog/entry/17307