Алгоритмы

DFS: Поиск в глубину

Цели урока

Понять отличие DFS от BFS
Реализовать рекурсивный и итеративный DFS
Применять DFS для поиска пути и циклов
Понимать времена входа/выхода

Предварительные знания

Стек (Stack)
Представление графов

Как выбраться из лабиринта без карты? Идти вперёд до тупика, потом назад до развилки. Этот интуитивный метод - основа DFS, одного из двух фундаментальных алгоритмов обхода графов.

Компиляторы: анализ зависимостей модулей
Игры: генерация лабиринтов
AI: игровые деревья (minimax)
Web crawlers: обход ссылок в глубину

Правило Тремо для лабиринтов и эпоха Хопкрофта и Тарьяна

Идея обхода в глубину старше компьютеров. В XIX веке французский инженер Шарль Пьер Тремо вывел правило прохождения лабиринтов вручную: помечай каждый коридор, по которому идёшь, не входи дважды в полностью помеченный коридор и возвращайся назад, когда свежих ходов не осталось. Эдуард Люка опубликовал метод в своих Récréations Mathématiques около 1882 года. Это и есть DFS с пометкой рёбер, за десятилетия до того, как любая машина смогла его выполнить. В информатику алгоритм пришёл в начале 1970-х, когда Джон Хопкрофт и Роберт Тарьян превратили DFS в точный инструмент. Их работа 1973 года показала, что один проход DFS вместе с временами входа и выхода решает целое семейство задач на графах за линейное время: двусвязные компоненты, мосты и точки сочленения, проверку планарности. Алгоритм Тарьяна 1972 года для сильно связных компонент и топологическая сортировка по времени выхода вырастают из того же обхода. То, что было трюком для лабиринтов, стало основой практической теории графов.

Идея: ныряем вглубь

**Представьте исследование пещеры.** Вы идёте вперёд по коридору до тупика. Потом возвращаетесь к последней развилке и пробуете другой путь. Это DFS - Depth-First Search.

**Ключевая структура - стек (Stack).** Рекурсия - это неявный стек вызовов, поэтому DFS естественно реализуется рекурсивно.

**BFS = очередь (Queue), DFS = стек (Stack или рекурсия).** Это единственное отличие в коде!

DFS vs BFS: в каком порядке посетятся вершины линейного графа A→B→C→D?

Реализация DFS

**Рекурсивная версия (проще):**

**Итеративная версия (со стеком):**

Версия	Плюсы	Минусы
Рекурсивная	Простой код, естественный	Stack overflow при глубине > 1000
Итеративная	Нет ограничения глубины	Более сложный код

**Python лимит рекурсии:** ~1000. Для больших графов используйте итеративную версию или `sys.setrecursionlimit()`.

Чем отличается код BFS от итеративного DFS?

Применения DFS

**1. Поиск пути (есть ли путь?):**

**2. Обнаружение цикла:**

**3. Подсчёт компонент связности:**

**4. Flood Fill (заливка):**

Для поиска КРАТЧАЙШЕГО пути лучше использовать:

Времена входа и выхода

**Продвинутая техника:** засекаем время входа (discovery) и выхода (finish) для каждой вершины.

**Применения меток времени:**

**Топологическая сортировка:** finish DESC
**Поиск мостов и точек сочленения**
**Классификация рёбер:** tree, back, forward, cross
**Сильно связные компоненты (SCC)**

**Скобочная структура:** интервалы [discovery, finish] либо вложены, либо не пересекаются. Никогда не частично перекрываются.

DFS находит кратчайший путь между двумя вершинами, если просто запомнить первый найденный путь.

DFS гарантирует только существование пути, длина зависит от порядка обхода соседей. Для кратчайшего пути в невзвешенном графе - BFS.

В простых примерах DFS часто действительно находит короткий путь, и это создаёт ложную интуицию. Но как только появляется ветвление с длинной 'неправильной' веткой, DFS уходит в неё до конца и возвращается, накопив длинный путь.

Если discovery[A]=1, finish[A]=10, discovery[B]=3, finish[B]=7, то: