DFS (Depth-first search)/Поиск в глубину
Published: 2023-11-25 21:57:05


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

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

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

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

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

Space complexity: O(V).

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

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

```java
    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) это некий метод или код, который мы хотим выполнить при посещении вершины. Конкретный код будет зависеть от задачи.

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

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

```java
    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 можно реализовать так:

```java
    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;
        }
    }
```

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

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

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

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

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

![](https://cdn-images-1.medium.com/max/2000/1*pnzGnrT9c1Xb_B1I0fyQNg.png)

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

Шаг 1:

![](https://cdn-images-1.medium.com/max/2000/1*1dzHPn60-2HeniMH4io7LQ.png)

Шаг 2:

![](https://cdn-images-1.medium.com/max/2000/1*DzRxImRAlvzsKCgvifSPFA.png)

Шаг 3:

![](https://cdn-images-1.medium.com/max/2000/1*jqBripMFzWdyVJsB20soSA.png)

Шаг 4:

![](https://cdn-images-1.medium.com/max/2000/1*42iOtHx0m5egM_5XmLpp0w.png)

Шаг 5:

![](https://cdn-images-1.medium.com/max/2000/1*TDxXrqviDEATtOxCMJru9w.png)

Шаг 6:

![](https://cdn-images-1.medium.com/max/2000/1*DmngMtv34PoS_wLFunqc8g.png)

Шаг 7:

![](https://cdn-images-1.medium.com/max/2000/1*Sp0EsX4pVtAir5Ddw1_zgg.png)

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

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

![](https://cdn-images-1.medium.com/max/2000/1*oYPXltrwOpa-x5CmL3uwsg.png)

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

![](https://cdn-images-1.medium.com/max/2000/1*VywH8yNkkyCzaxLfMTYVNg.png)

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

![](https://cdn-images-1.medium.com/max/2000/1*smlMmZhDCjWkWnUAxmjoXA.png)

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

![](https://cdn-images-1.medium.com/max/2000/1*VX7bSBHZVHUP0PV0slOp1w.png)

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

![](https://cdn-images-1.medium.com/max/2000/1*Lcx7pAdybTE4c7y6rnaoyQ.png)

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

![](https://cdn-images-1.medium.com/max/2000/1*L0zgcr5mjL_mE6kTBg1b4Q.png)

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

![](https://cdn-images-1.medium.com/max/2000/1*tqMHmX42tw1jVzSsyGnx6w.png)

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

![](https://cdn-images-1.medium.com/max/2000/1*7qLVtyu9vrNUcA-pEgSSdw.png)

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

![](https://cdn-images-1.medium.com/max/2000/1*X9tVWUntcU-k8x2ZbxSFPg.png)