2

我正在解决这个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 项目的完整代码。

4

2 回答 2

3

检查你的graph.adjacencies.get(V)，他们对这两种情况的反应是否相同？如果是这样，那么递归调用和堆栈调用将给出不同的结果。例如，像这样的树：

      1
    2   3
  4

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

于 2012-10-16T12:03:24.113 回答
1

因为堆栈。它是先进后出的，因此您将按照将它们添加到堆栈的相反顺序遍历节点的子节点。

假设根的 2 个孩子是 A 和 B，按此顺序（从左到右）。

第一个算法：

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

第二个算法：

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

您可以将 Stack 替换为 FIFO 的 Queue 实现，它应该没问题。

于 2011-10-07T15:26:06.720 回答