DFS (Depth-first search)/Поиск в глубину

Граф — это совокупность вершин и связей между ними (ребер).

Есть два основных метода обхода графа: Поиск в глубину (dfs/Depth-first search)и Поиск в ширину(bfs/breadth-first search).

Стратегия поиска в глубину заключается в том, чтобы вначале пойти вглубь графа, насколько это возможно. В то время как при поиске в ширину, граф обходится, как бы “по слоям”. Сначала все соседи от начальной вершины, потом соседи соседей и т.д.

Есть две реализации алгоритма поиска в глубину: рекурсивная и через стек.

Временная сложность алгоритма: O(E + V).

Space complexity: O(V).

V — число вершин в графе, E — число ребер.

Реализация через рекурсию:

    void dfs(Node root, Set<Node> visited) {
      if (root == null) {
        return;
      }
      visit(root);
      visited.add(root);
      for (Node neighbour : root.getNeighbours()) {
        if (!visited.contains(neighbour)) {
          dfs(neighbour, visited);
        }
      }
    }

Node — это class вершины графа. Нам необходимо хранить список уже посещенных вершин, чтобы не ходить по одним и тем же вершинам кругами.

visit(Node node) это некий метод или код, который мы хотим выполнить при посещении вершины. Конкретный код будет зависеть от задачи.

Работает алгоритм так: посещаем первую вершину, помечаем ее как посещенную, смотрим на список ее соседей и если мы их еще не посещали, то рекурсивно вызываем функцию уже для соседей.

Реализация при помощи стека:

    void dfs(Node root) {
        if (root == null) {
          return;
        }
        Set<Node> visited = new HashSet<>();
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        visited.add(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            visit(node);
            for (Node neighbour : node.getNeighbours()) {
              if (!visited.contains(neighbour)) {
                visited.add(neighbour);
                stack.push(neighbour);
              }
            }
        }
    }

Со стеком. Помещаем первую вершину в стек, помечаем ее как посещенную. Пока стек не пуст: получаем вершину графа из стека, посещаем ее, смотрим на ее соседей, те вершины, которые мы еще не посетили, помечаем их как посещенными и помещаем в стек.

class Node можно реализовать так:

    class Node {
        private int value;
        private final List<Node> neighbours;

        public Node(int value, List<Node> neighbours) {
            this.value = value;
            this.neighbours = neighbours;
        }

        public List<Node> getNeighbours() {
            return this.neighbours;
        }

        public int getValue() {
            return this.value;
        }
    }

Или, для простоты, на собеседовании можно себе представлять так:

    class Node {
        int value;
        List<Node> neighbours;

        public Node(int value, List<Node> neighbours) {
            this.value = value;
            this.neighbours = neighbours;
        }
    }

Это позволит обращаться к полям класса:

    Node node = ...
    node.value //Получить значение
    node.neighbours // Получить всех соседей

Давайте посмотрим по шагам как будет работать рекурсивный поиск в глубину на таком графе:

Я буду помечать зеленым цветом уже посещенные вершины (visited):

Шаг 1:

Шаг 2:

Шаг 3:

Шаг 4:

Шаг 5:

Шаг 6:

Шаг 7:

Для реализации через стек, обход будет несколько другой. Он вначале пойдет вправо. Но также, обход будет сначала на максимальную глубину. 1->3->6->2->5->4->7

Посмотрим более подробно на состояние стека и последовательность посещения для реализации DFS через стек. Посещенные вершины также буду помечать зеленым.

Помечаем первую вершину, добавляем ее в стек. В цикле на первой итерации достаем ее из стека и посещаем (visit(node)).

Соседние вершины к 1 это вершины 2 и 3. Они еще не помечены, помещаем их в стек и помечаем.

На следующей итерации цикла while достаем из вершины стека 3 и посещаем ее. Смежные/соседние вершины к 3 это 1 и 6. 1 уже помечена. Поэтому в стек добавляем 6 и помечаем ее.

Достаем из стека 6 и посещаем ее. У 6 только одна смежная вершина — 3. Но она уже помечена. Поэтому переходим на следующую итерацию цикла while.

Достаем из стека 2. Посещаем ее. Смотрим на ее смежные вершины: 1, 4, 5. 1 уже помечена. Поэтому помечаем 4 и 5 и помещаем их в стек.

Достаем из стека 5. Посещаем ее. У 5 одна смежная вершина 2. Но она уже помечена, поэтому ничего не добавляем в стек.

Достаем 4 из стека, посещаем ее. У нее смежные это 2 и 7. 2 уже помечена. Поэтому помечаем 7 и помещаем ее в стек.

Достаем 7 из стека. Посещаем ее. У 7 одна смежная вершина — 4. Она уже помечена. На следующей итерации цикла while стек будет пуст — алгоритм закончен.