Блог

Я решаю эту проблему 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.

Проверьте graph.adjacencies.get(V) , дают ли они вам одинаковый ответ в обоих случаях? Если это так, то рекурсивный вызов и вызов стека дадут разные результаты. Например, дерево, подобное:

       1
    2   3
  4
  

будет иметь порядок 1->3->2->4 для версии стека и порядок 1->2->4->3 для рекурсивной версии, предполагая graph.adjacencies.get(V) , что всегда сначала возвращается левый дочерний элемент.

Из-за стека. Это первый вход, последний выход, поэтому вы будете просматривать дочерние узлы в обратном порядке, в котором вы добавили их в стек.

Скажем, 2 дочерних элемента корня — это A и B, в таком порядке (слева направо).

Первый алгоритм:

1. Обрабатывать корень
2. Добавить A в стек
3. Добавить B в стек
4. Всплывающее окно из стека (так что B, потому что стек FILO)

Второй алгоритм:

1. Обрабатывать корень
2. Обрабатывать
3. … обрабатывать дочерние элементы A
4. Обработайте B

Вы можете заменить свой стек реализацией очереди, которая является FIFO, и все должно быть в порядке.