Что такое поиск в глубину (DFS)?

Question

Accepted Answer

**DFS** исследует граф, проходя как можно глубже по каждой ветви перед возвратом. Он использует **стек** (часто стек вызовов через рекурсию) и посещает полный путь перед исследованием альтернатив.

## Идея

Из узла рекурсивно перейдите к непосещённому соседу и идите глубже; когда застрянете, вернитесь и попробуйте другую ветвь.

## Пример

```python
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nbr in graph[node]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)  # go deeper first
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
dfs(graph, 'A')                        # -> ['A', 'B', 'D', 'C']
```

## BFS vs DFS

| | BFS | DFS |
|---|-----|-----|
| Структура | очередь | стек / рекурсия |
| Находит | кратчайший (невзвешенный) | любой путь |
| Память | O(V) граница | O(глубина) |
| Подходит для | кратчайшие пути, уровни | циклы, топо сортировка, компоненты |

## Сложность

- **Время:** O(V + E). **Пространство:** O(V) (глубина рекурсии + посещённые).

## Подводные камни

Глубокие графы могут вызвать переполнение стека рекурсии — используйте явный стек. Отслеживайте `visited` для обработки циклов.

## Почему это важно

DFS лежит в основе обнаружения циклов, топологической сортировки, связных компонентов и генерации лабиринта/пути.

Его рекурсивная элегантность делает код деревьев и графов лаконичным.

Знание того, когда поиск в глубину превосходит поиск в ширину, — это основной навык в алгоритмах на графах.

	BFS	DFS
Структура	очередь	стек / рекурсия
Находит	кратчайший (невзвешенный)	любой путь
Память	O(V) граница	O(глубина)
Подходит для	кратчайшие пути, уровни	циклы, топо сортировка, компоненты