12.1 Поиск в глубину (Depth-First Search)¶

Поиск в глубину (DFS) — это один из базовых алгоритмов обхода графа. Его идея проста: мы всегда идём как можно глубже по одному пути, пока это возможно, а затем возвращаемся назад и пробуем другие направления.

Алгоритм запоминает уже посещённые вершины, чтобы не обрабатывать одну и ту же вершину несколько раз.

Как работает DFS¶

Представим граф:

graph LR
    A["1"] --- B["2"]
    A --- D["4"]
    B --- C["3"]
    C --- E["5"]
    D --- E

Запустим поиск из вершины 1.

Шаги:¶

1. Начинаем с вершины 1
2. Переходим в 2
3. Из 2 идём в 3
4. Из 3 идём в 5
5. У 5 нет новых соседей → возвращаемся назад
6. Возвращаемся к 1 и идём в 4
7. Все вершины посещены → алгоритм завершён

Основная идея: алгоритм проходит вглубь, а затем возвращается назад.

Основные свойства¶

• Каждая вершина посещается ровно один раз
• Каждое ребро рассматривается один раз
• Время работы:

[ O(n + m) ]

где:

• ( n ) — количество вершин
• ( m ) — количество рёбер

Реализация через рекурсию¶

DFS удобно реализовать с помощью рекурсии.

vector<int> g[N];
bool used[N];

void dfs(int v) {
    if (used[v]) return;

    used[v] = true;

    // обработка вершины v

    for (int u : g[v]) {
        dfs(u);
    }
}

Что происходит внутри¶

Можно представить DFS как стек вызовов:

flowchart TD
    A["dfs(1)"] --> B["dfs(2)"]
    B --> C["dfs(3)"]
    C --> D["dfs(5)"]
    D --> E["возврат"]
    E --> F["dfs(4)"]

• Каждый вызов функции — это переход вперёд
• Возврат из функции — это откат назад

Где используется DFS¶

Поиск в глубину применяется для:

• проверки связности графа
• поиска компонент связности
• обнаружения циклов
• топологической сортировки
• обхода деревьев
• задач перебора

Интуиция¶

DFS можно представить как исследование лабиринта:

• движение вперёд, пока это возможно
• возврат назад при тупике
• поиск альтернативного пути

Итог¶

• DFS — простой алгоритм обхода графа
• Реализуется через рекурсию или стек
• Работает за линейное время
• Используется во многих задачах