迭代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

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

-> Netbeans项目的完整代码。

Answer 1

检查您的graph.adjacencies.get(V)，他们是否为两种情况给出相同的响应?如果是这样，那么递归调用和堆栈调用将给出不同的结果。例如，这样的树:

      1
    2   3
  4

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

Answer 2

因为堆栈。它是先入后出的，所以你将以相反的顺序来遍历节点的子节点，而你将它们添加到堆栈中。

假设根结点的两个子结点是A和B，按照从左到右的顺序。

第一个算法:

1. 处理根
2. 添加A到栈
3. 添加B到栈
4. 从堆栈弹出(所以是B，因为堆栈是FILO)

第二个算法:

1. 处理根
2. 处理
3. …处理A的孩子
4. 处理B

你可以用队列实现取代你的堆栈，这是FIFO，它应该是好的。