迭代DFS中的奇数排序与递归DFS

Question

我正在解决这个dfs/bfs问题。

我编写了DFS的迭代版本和递归版本。

节点访问的顺序是不同的，我不明白为什么。

迭代DFS：

static void DFS (Integer root, Graph graph){

      //  System.out.println("DFS");

        HashSet <Integer> explored = new HashSet<Integer>();
             explored.add(root);

        Stack<Integer> stack = new Stack<Integer>();
              stack.add(root);

        int v; int w;


        while (!stack.isEmpty()){

            v=stack.pop();
            explored.add(v);

            System.out.print(v + " ");
           // for (int i=graph.adjacencies.get(v).size()-1; i>=0; i--) {
            for (int i=0; i < graph.adjacencies.get(v).size(); i++) {
                w = graph.adjacencies.get(v).get(i);

                if (!explored.contains(w)){

                    stack.add(w);
                    explored.add(w);
                }
            }

        }System.out.println();
    } 

递归DFS：

static void DFS_2 (Integer root, Graph graph){

//        System.out.println("DFS_2");

        int v; int w;

        v = root;

        graph.explored.add(v);

            System.out.print(v + " ");
            for (int i=0; i < graph.adjacencies.get(v).size(); i++) {

                w = graph.adjacencies.get(v).get(i);

                if (!graph.explored.contains(w)){

                    graph.explored.add(w);
                    DFS_2(w, graph);
                }
            }


    }

关于教程问题，我在迭代式DFS版本上的输出是

1 4 3 2 6

而它应该是(根据问题示例输出和递归版本)：

1 3 2 6 4

这是怎么回事？为什么消除递归会改变访问节点的顺序？

->Full code on a Netbeans project.

Answer 1

检查你的graph.adjacencies.get(V)，这两种情况下他们给你的回复是一样的吗？如果是这样，那么递归调用和堆栈调用将产生不同的结果。例如，如下所示的树：

      1
    2   3
  4

堆栈版本的顺序为1->3->2->4，递归版本的顺序为1->2->4->3，假设graph.adjacencies.get(V)总是首先返回左子对象。

Answer 2

因为有了堆栈。它是First- in，Last-Out，因此您将按照将节点的子节点添加到堆栈的相反顺序来查看它们。

假设根的两个孩子是A和B，按照这个顺序(从左到右)。

第一种算法：

1. 句柄根
2. 将A添加到堆栈
3. 将B添加到堆栈
4. 从堆栈中弹出(因此是B，因为堆栈是FILO)

第二种算法：

1. Handle root
2. Handle A
3. ...handle A's kids
4. Handle B

(处理A的孩子和处理B)

你可以用一个先进先出的队列实现替换你的Stack，它应该没问题。