Алгоритм поиска в глубину

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

История

Идея систематического обхода графа в глубину впервые была формализована в середине XX века в рамках развития теории графов и алгоритмов. Одним из первых алгоритмов, использующих принцип поиска в глубину, стал алгоритм Тарьяна для поиска компонент сильной связности в ориентированном графе, опубликованный Робертом Тарьяном в 1972 году. Однако сам метод обхода в глубину был известен и ранее — он применялся в задачах лабиринтов и в ранних компьютерных играх, таких как «Лабиринт» (1950-е годы). В 1970-х годах алгоритм был включён в стандартные учебные курсы по алгоритмам и структурам данных, а его реализация на языках программирования, таких как Pascal и C, стала классическим упражнением.

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

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

Псевдокод (рекурсивная версия)

`` DFS(vertex): mark vertex as visited for each neighbor of vertex: if neighbor is not visited: DFS(neighbor) ``

Псевдокод (итеративная версия с использованием стека)

`` DFS(start): stack = [start] while stack is not empty: vertex = stack.pop() if vertex is not visited: mark vertex as visited for each neighbor of vertex: if neighbor is not visited: stack.push(neighbor) ``

Характеристики

Временная сложность

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

Пространственная сложность

Пространственная сложность алгоритма зависит от реализации:

• Рекурсивная версия: O(V) в худшем случае (глубина рекурсивного стека может достигать числа вершин, например, в случае линейного графа).
• Итеративная версия: O(V) для стека, а также O(V) для хранения информации о посещённых вершинах.

Свойства

• Полнота: Алгоритм не гарантирует нахождения кратчайшего пути (в отличие от поиска в ширину), но гарантирует обход всех достижимых вершин.
• Оптимальность: Не является оптимальным для поиска кратчайшего пути в невзвешенных графах, так как может найти более длинный путь.
• Завершаемость: Гарантированно завершается для конечных графов. Для бесконечных графов может не завершиться, если не ограничить глубину.

Применение

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

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

DFS позволяет найти все компоненты связности неориентированного графа. Для этого алгоритм запускается из каждой непосещённой вершины, и каждая такая итерация выделяет одну компоненту.

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

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

Поиск циклов

DFS может обнаруживать циклы в графе. Для этого в процессе обхода отслеживаются состояния вершин: «не посещена», «в процессе обхода» и «посещена». Если во время обхода встречается вершина в состоянии «в процессе обхода», это означает наличие цикла.

Поиск мостов и точек сочленения

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

Решение задач на графах

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

Искусственный интеллект

В области искусственного интеллекта DFS используется в алгоритмах поиска в пространстве состояний, таких как поиск в глубину с ограничением (Depth-Limited Search) и итеративное углубление (Iterative Deepening Depth-First Search, IDDFS), которые применяются в игровых программах (например, шахматы, головоломки) и в планировании.

Разновидности

Поиск в глубину с ограничением (Depth-Limited Search, DLS)

Модификация DFS, в которой задаётся максимальная глубина обхода. Это позволяет избежать бесконечного цикла в графах с циклами и ограничить использование памяти. Однако алгоритм может не найти решение, если оно находится глубже заданного предела.

Итеративное углубление (Iterative Deepening DFS, IDDFS)

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

Поиск в глубину на ориентированных графах

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

Реализация на языках программирования

Пример на Python (рекурсивная версия)

``python def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for neighbor in graph[start]: if neighbor not in visited: dfs(graph, neighbor, visited) return visited ``

Пример на C++ (итеративная версия)

```cpp

include <iostream>

include <vector>

include <stack>

void dfs(const std::vector<std::vector<int>>& graph, int start) { std::vector<bool> visited(graph.size(), false); std::stack<int> stack; stack.push(start); while (!stack.empty()) { int vertex = stack.top(); stack.pop(); if (!visited[vertex]) { visited[vertex] = true; std::cout << vertex << " "; for (int neighbor : graph[vertex]) { if (!visited[neighbor]) { stack.push(neighbor); } } } } } ```

Сравнение с другими алгоритмами

Поиск в ширину (BFS)

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

Алгоритм Дейкстры

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

Критика

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

Интересные факты

• Алгоритм поиска в глубину лежит в основе многих алгоритмов генерации лабиринтов, например, алгоритма «случайного DFS», который создаёт лабиринты с минимальным количеством тупиков.
• DFS используется в программах для проверки орфографии (поиск слов в словаре, представленном в виде дерева).
• В операционных системах DFS применяется для обхода файловой системы (например, команда find в Unix/Linux).

Источники

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. «Алгоритмы: построение и анализ» (Introduction to Algorithms), 3-е издание, 2009.
• Роберт Седжвик, Кевин Уэйн. «Алгоритмы на Java», 4-е издание, 2011.
• Стивен С. Скиена. «Алгоритмы. Руководство по разработке», 2-е издание, 2008.
• Статья «Depth-first search» в Википедии (англоязычная версия), 2024.