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 стек будет пуст — алгоритм закончен.