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

Поиск в глубину (англ. Depth-First Search, DFS) — это один из фундаментальных алгоритмов обхода графа, который систематически посещает все вершины, двигаясь вдоль рёбер от начальной вершины вглубь, насколько это возможно, прежде чем вернуться назад. Алгоритм относится к классу стратегий поиска без информации (uninformed search) и широко применяется в теории графов, информатике и смежных дисциплинах для решения задач, связанных с анализом связности, поиском путей, топологической сортировкой и проверкой наличия циклов.

Принцип работы

Основная идея поиска в глубину заключается в рекурсивном или итеративном обходе графа с использованием стека (явного или неявного, через рекурсию). Алгоритм начинает с выбранной стартовой вершины, помечает её как посещённую, а затем последовательно переходит к первой непосещённой смежной вершине. Процесс повторяется: из новой вершины алгоритм углубляется дальше, пока не достигнет вершины, у которой нет непосещённых соседей. В этот момент происходит возврат (backtracking) к предыдущей вершине, и алгоритм продолжает поиск среди оставшихся непосещённых смежных вершин. Обход завершается, когда все вершины, достижимые из начальной, будут посещены.

Рекурсивная реализация

Рекурсивная версия DFS естественным образом использует стек вызовов. Псевдокод рекурсивного поиска в глубину для графа, представленного списками смежности, выглядит следующим образом:

`` DFS(вершина v): отметить v как посещённую для каждой смежной вершины u из v: если u не посещена: DFS(u) ``

Для предотвращения зацикливания в графах с циклами необходимо вести учёт посещённых вершин. В случае ориентированных графов дополнительно может храниться статус вершины (белая — не посещена, серая — в процессе обхода, чёрная — обработана) для обнаружения циклов.

Итеративная реализация

Итеративная версия использует явный стек. Алгоритм помещает стартовую вершину в стек и, пока стек не пуст, извлекает вершину, проверяет, не была ли она посещена, и, если нет, помечает её и добавляет в стек всех её непосещённых соседей. Важно отметить, что порядок обхода может отличаться от рекурсивного из-за порядка добавления соседей в стек (LIFO — «последним пришёл — первым вышел»).

`` DFS_итеративный(граф G, стартовая_вершина s): создать стек S поместить s в S пока S не пуст: v = извлечь из S если v не посещена: отметить v как посещённую для каждой смежной вершины u из v: если u не посещена: поместить u в S ``

Свойства и характеристики

Сложность

Временная сложность поиска в глубину составляет O(V + E), где V — количество вершин, E — количество рёбер графа. Это объясняется тем, что каждая вершина посещается ровно один раз, и каждое ребро рассматривается один раз (для графа, представленного списками смежности). Для матрицы смежности сложность возрастает до O(V²). Пространственная сложность в худшем случае составляет O(V) для хранения стека и меток посещённых вершин.

Полнота и оптимальность

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

Порядок обхода

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

• Прямой порядок (pre-order): вершина обрабатывается до рекурсивного вызова для её соседей.
• Обратный порядок (post-order): вершина обрабатывается после возврата из рекурсивных вызовов.

Применение

Поиск в глубину лежит в основе множества алгоритмов и задач обработки графов.

Поиск компонент связности

DFS позволяет найти все компоненты связности неориентированного графа. Запуская алгоритм из каждой непосещённой вершины, можно выделить множество вершин, достижимых друг из друга. Аналогично для ориентированных графов DFS используется для поиска сильно связных компонент (алгоритм Тарьяна или Косарайю).

Топологическая сортировка

В ориентированных ациклических графах (DAG) DFS с записью вершин в порядке завершения их обработки (post-order) даёт топологический порядок. Вершины, обработанные позже, располагаются раньше в топологическом порядке, что используется при планировании задач, компиляции (определение порядка вычисления выражений) и анализе зависимостей.

Обнаружение циклов

В ориентированных графах наличие обратного ребра (ребра, ведущего к серой вершине) свидетельствует о наличии цикла. DFS с раскраской вершин (белый, серый, чёрный) позволяет эффективно детектировать циклы.

Поиск путей и лабиринты

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

Задачи на деревьях

В бинарных и n-арных деревьях DFS соответствует обходу в глубину (pre-order, in-order, post-order). Эти обходы используются для сериализации деревьев, вычисления выражений (абстрактные синтаксические деревья), поиска элементов и проверки свойств (например, является ли дерево симметричным).

Анализ графов в социальных сетях и веб-графах

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

Пример работы

Рассмотрим неориентированный граф с вершинами A, B, C, D, E и рёбрами: A-B, A-C, B-D, C-E. Стартовая вершина — A.

1. Посещаем A. Смежные: B, C. Переходим к B.
2. Посещаем B. Смежные: A (посещена), D. Переходим к D.
3. Посещаем D. Смежные: B (посещена). Возврат к B.
4. У B нет непосещённых соседей. Возврат к A.
5. У A остался непосещённый сосед C. Переходим к C.
6. Посещаем C. Смежные: A (посещена), E. Переходим к E.
7. Посещаем E. Смежные: C (посещена). Возврат к C.
8. У C нет непосещённых соседей. Возврат к A.
9. Все вершины посещены. Конец.

Порядок обхода: A, B, D, C, E. Если бы порядок смежных вершин был другим (например, сначала C, потом B), порядок мог бы быть A, C, E, B, D.

Варианты и модификации

• Итеративное углубление в глубину (Iterative Deepening Depth-First Search, IDDFS): комбинирует полноту BFS и экономию памяти DFS. Алгоритм выполняет DFS с ограничением глубины, постепенно увеличивая это ограничение, пока цель не будет найдена. IDDFS полон и оптимален в невзвешенных графах.
• Поиск в глубину с ограничением (Depth-Limited Search, DLS): DFS с фиксированным максимальным уровнем глубины, используется для предотвращения бесконечного углубления.
• Двунаправленный поиск в глубину: применяется для поиска пути между двумя вершинами, запуская DFS одновременно из обеих вершин и останавливаясь при пересечении.

Критика и ограничения

Основным недостатком DFS является его неоптимальность и потенциальная неполнота в бесконечных или очень больших графах. При отсутствии ограничения глубины алгоритм может бесконечно углубляться в одну ветвь, не находя решения. Кроме того, DFS не гарантирует нахождение кратчайшего пути, что делает его непригодным для задач, где важна длина маршрута. В графах с большим количеством вершин рекурсивная реализация может привести к переполнению стека вызовов.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013.
• Седжвик Р., Уэйн К. Алгоритмы на Java. — 4-е изд. — М.: Вильямс, 2016.
• Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. — М.: Вильямс, 2000.
• Russell S., Norvig P. Artificial Intelligence: A Modern Approach. — 4th ed. — Pearson, 2020.