В прошлом уроке мы разобрали обход в ширину — BFS. Он двигался слоями: сначала все соседи стартовой вершины, потом все соседи соседей. Очередь держала «текущий горизонт». BFS гарантирует кратчайший путь в невзвешенном графе, и это его главное достоинство. Но есть целый класс задач, где «ширина» не нужна. Нам нужна глубина: войти в граф как можно дальше по одному пути, упереться в тупик и только тогда вернуться.

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

Разберём работу алгоритма на конкретном примере. Вот граф из шести вершин:

Список смежности: 0: [1, 2], 1: [0, 3, 4], 2: [0, 4], 3: [1, 5], 4: [1, 2, 5], 5: [3, 4].

Трассировка DFS с вершины 0:

Шаг 1: посещаем 0, смотрим на первого соседа — 1.

Шаг 2: уходим в 1, первый непосещённыйососед — 3.

Шаг 3: уходим в 3, первый непосещённый сосед — 5 (сосед 1 уже посещён).

Шаг 4: уходим в 5, соседи 3 и 4; 3 посещён, уходим в 4.

Шаг 5: уходим в 4, соседи 1, 2, 5; 1 и 5 посещены, уходим в 2.

Шаг 6: уходим в 2, соседи 0 и 4 — оба посещены. Тупик. Возврат.

Итог: 0 → 1 → 3 → 5 → 4 → 2.

Ключевое отличие от BFS: DFS дошёл до 5 и 4 за 3–4 шага, хотя от 0 они находятся на том же расстоянии, что и 2. BFS посетил бы сначала 1 и 2 (расстояние 1), потом 3 и 4 (расстояние 2), потом 5 (расстояние 3). DFS не гарантирует кратчайший путь — он гарантирует, что дойдёт до конца ветви. Реализация DFS делается двумя способами. Первый — рекурсивный, самый компактный. Рекурсия сама создаёт неявный стек вызовов:

var graph = new Dictionary<int, List<int>>
{
    [0] = new List<int> { 1, 2 },
    [1] = new List<int> { 0, 3, 4 },
    [2] = new List<int> { 0, 4 },
    [3] = new List<int> { 1, 5 },
    [4] = new List<int> { 1, 2, 5 },
    [5] = new List<int> { 3, 4 }
};

var visited = new HashSet<int>();

void DfsRecursive(int v)
{
    visited.Add(v);           // помечаем вершину посещённой
    Console.Write(v + " ");   // обрабатываем

    foreach (var neighbor in graph[v])
    {
        if (!visited.Contains(neighbor))
            DfsRecursive(neighbor);  // рекурсивно уходим в глубину
    }
}

DfsRecursive(0);
// Вывод: 0 1 3 5 4 2

Структура проста: входим в вершину, помечаем её, обходим каждого непосещённого соседа тем же методом. Когда у вершины не остаётся непосещённых соседей — метод завершается и мы возвращаемся на уровень выше. Это и есть «backtracking» — возврат по стеку вызовов.

Важный момент: HashSet<int> visited необходим всегда. Без него в графе с циклами рекурсия зайдёт в бесконечный цикл. В дереве (без циклов) можно обойтись без него — именно поэтому в уроках по деревьям visited не использовался.

Второй способ — итеративный, с явным Stack<int>. По сути, это то же самое, что BFS, но вместо Queue мы берём Stack:

void DfsIterative(int start)
{
    var visited = new HashSet<int>();
    var stack = new Stack<int>();

    stack.Push(start);

    while (stack.Count > 0)
    {
        int v = stack.Pop();  // берём последний добавленный (LIFO)

        if (visited.Contains(v))
            continue;         // могли добавить дважды — пропускаем

        visited.Add(v);
        Console.Write(v + " ");

        // Добавляем соседей в обратном порядке, чтобы сохранить
        // тот же порядок обхода, что и рекурсивный DFS
        var neighbors = graph[v];
        for (int i = neighbors.Count - 1; i >= 0; i--)
        {
            if (!visited.Contains(neighbors[i]))
                stack.Push(neighbors[i]);
        }
    }
}

DfsIterative(0);
// Вывод: 0 1 3 5 4 2

Механика: кладём стартовую вершину в стек. На каждом шаге берём вершину с вершины стека (Pop), обрабатываем её и кладём её соседей. Поскольку стек работает по принципу LIFO (последним пришёл — первым ушёл), следующей обрабатывается последний добавленный сосед, то есть алгоритм уходит вглубь. Проверка visited.Contains(v) делается после Pop, а не до Push: одна и та же вершина может оказаться в стеке несколько раз (добавлена разными соседями), поэтому при извлечении нужно повторно проверить.

DFS применяется значительно шире, чем просто «обойти все вершины». Разберём ключевые применения.

Поиск цикла в неориентированном графе. Если во время DFS мы встречаем соседа, который уже посещён и при этом не является родителем текущей вершины — цикл найден. Родителя нужно отслеживать отдельно, чтобы не спутать «обратное» ребро (цикл) с ребром к непосредственному предку:

bool HasCycleDfs(int v, int parent, HashSet<int> visited,
                  Dictionary<int, List<int>> g)
{
    visited.Add(v);

    foreach (var neighbor in g[v])
    {
        if (!visited.Contains(neighbor))
        {
            // Уходим глубже; если там нашли цикл — поднимаем true
            if (HasCycleDfs(neighbor, v, visited, g))
                return true;
        }
        else if (neighbor != parent)
        {
            // Посещённый сосед, не наш родитель — обратное ребро = цикл
            return true;
        }
    }
    return false;
}

// Проверяем граф из 4 вершин с циклом 0-1-2-0
var cyclic = new Dictionary<int, List<int>>
{
    [0] = new List<int> { 1, 2 },
    [1] = new List<int> { 0, 2 },
    [2] = new List<int> { 0, 1, 3 },
    [3] = new List<int> { 2 }
};

bool found = HasCycleDfs(0, -1, new HashSet<int>(), cyclic);
Console.WriteLine(found); // True

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

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

int componentCount = 0;
var visited = new HashSet<int>();

for (int v = 0; v < graph.Count; v++)
{
    if (!visited.Contains(v))
    {
        DfsRecursive(v);  // обходит всю компоненту
        componentCount++;
    }
}
Console.WriteLine($"Компонент: {componentCount}");

Поиск всех путей. DFS с backtracking позволяет найти все пути из точки A в точку B. На каждом шаге добавляем вершину в текущий путь, рекурсируем, после возврата убираем её обратно. Это классический паттерн рекурсии с отменой действия:

void FindAllPaths(int v, int target, List<int> path, HashSet<int> visited)
{
    visited.Add(v);
    path.Add(v);

    if (v == target)
    {
        Console.WriteLine(string.Join(" → ", path));
    }
    else
    {
        foreach (var neighbor in graph[v])
            if (!visited.Contains(neighbor))
                FindAllPaths(neighbor, target, path, visited);
    }

    // Backtracking: убираем вершину при возврате
    path.RemoveAt(path.Count - 1);
    visited.Remove(v);
}

Топологическая сортировка — упорядочивание вершин ориентированного графа так, чтобы все рёбра шли «слева направо». Нужна для систем сборки (make, gradle), планировщиков задач, компиляторов. DFS — основа классического алгоритма: когда все потомки вершины обработаны, добавляем её в начало результата. Это тема отдельного урока, но важно знать, что DFS — инструмент, без которого топологическую сортировку не построить.

Лабиринты. Граф клеток лабиринта — классическое применение DFS. Алгоритм идёт по первому возможному направлению до тупика, возвращается и пробует следующее. Именно DFS лежит в основе большинства алгоритмов генерации лабиринтов.

Теперь о терминах, которые встретите в алгоритмических задачах. Во время DFS рёбра делятся на два типа. Древесные рёбра (tree edges) — те, по которым DFS реально перемещался (обнаружил новую вершину). Они образуют «DFS-дерево» — остов графа с точки зрения обхода. Обратные рёбра (back edges) — те, что ведут к уже посещённой вершине. В неориентированном графе каждое обратное ребро означает цикл. В ориентированном графе наличие обратного ребра тоже означает цикл — и именно это используется при топологической сортировке: если граф содержит обратное ребро, топосортировка невозможна.

Сложность DFS такая же, как у BFS: O(V + E). Каждая вершина посещается ровно один раз (O(V)), каждое ребро рассматривается ровно два раза в неориентированном графе (O(E)). Память — O(V) для visited плюс O(V) для стека (в худшем случае — весь граф в стеке, когда граф — длинная цепь).

Сравнение BFS и DFS — короткое, но важное:

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

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

Рекурсивный DFS использует стек вызовов: посещаем вершину, помечаем её в HashSet<int> visited, рекурсивно обходим каждого непосещённого соседа.

Итеративный DFS использует явный Stack<int>: кладём стартовую вершину, на каждом шаге извлекаем вершину и кладём её непосещённых соседей. Проверяем visited после Pop, а не до Push.

HashSet visited обязателен для графов с циклами — без него рекурсия зайдёт в бесконечный цикл.

Применения DFS: поиск цикла (обратное ребро к непредку), компоненты связности (новый запуск = новая компонента), все пути из A в B (backtracking), топологическая сортировка, генерация лабиринтов.

Древесные рёбра — те, по которым DFS прошёл в новую вершину. Обратные рёбра — те, что ведут к уже посещённой вершине; их наличие означает цикл.

Сложность DFS: O(V + E) по времени, O(V) по памяти.

BFS vs DFS: BFS даёт кратчайший путь в невзвешенном графе; DFS — инструмент для исследования структуры: циклы, топосорт, все пути. Рекурсивный DFS опасен на графах с ~10 000+ вершин в одной цепочке — используйте итеративный вариант.