Поиск в глубину
Поиск в глубину — это способ обхода дерева или графа, при котором алгоритм сначала проходит как можно дальше по одной ветви, а затем возвращается назад и исследует другие ветви.
Как работает алгоритм
Перед переходом в вершину её помечают как посещённую. Это особенно важно в графе: без такой отметки алгоритм может бесконечно ходить по циклу. В дереве циклов нет, но отметки всё равно часто используют в общей реализации DFS.
- Начать с выбранной начальной вершины.
- Выбрать соседнюю непосещённую вершину и перейти в неё.
- Повторять переход, пока есть непосещённые соседи.
- При отсутствии таких соседей вернуться назад и продолжить перебор.
Для графа с \(V\) вершинами и \(E\) рёбрами время работы DFS обычно равно \(O(V+E)\): каждая вершина и каждое ребро обрабатываются ограниченное число раз. Для дерева из \(n\) вершин это \(O(n)\). Дополнительная память зависит от глубины обхода и может достигать \(O(V)\).
Пусть из вершины 1 можно попасть в 2 и 3, а из 2 — в 4. При порядке соседей слева направо поиск пройдёт так: 1 → 2 → 4, затем вернётся в 2, вернётся в 1 и перейдёт в 3. В отличие от обхода в ширину, вершина 3 не посещается сразу после 1.
Бэктрекинг использует идею углубления и возврата, но обычно перебирает варианты решения и может отменять сделанные выборы. DFS — прежде всего способ обойти вершины графа или дерева; он не обязан искать решение среди вариантов.
В каком порядке DFS обойдёт вершины, если из 1 идут рёбра в 2 и 3, из 2 — в 4, а соседи выбираются по возрастанию?
Главное
- DFS идёт как можно глубже по текущей ветви, затем возвращается назад.
- Для графа нужны отметки посещённых вершин, чтобы не зациклиться.
- Сложность обхода — \(O(V+E)\); реализовать его можно рекурсией или стеком.