Другой обход, другой порядок

В прошлом уроке мы разобрали BFS: он идёт по слоям, сначала все соседи старта, потом соседи соседей, и так далее. Порядок обеспечивает кратчайшие пути по числу рёбер, и на этом строится его главное применение. Теперь посмотрим на второй классический обход — DFS, обход в глубину. Он устроен принципиально иначе: вместо того чтобы расширяться по слоям, он углубляется по одной ветви, пока может, а потом возвращается и пробует следующую. Словно человек в лабиринте, который идёт до тупика, возвращается к последней развилке и пробует другой поворот.

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

Здесь важное отличие от BFS, которое стоит уяснить сразу. BFS минимизирует число рёбер от старта до каждой вершины. DFS этого не делает. В нашем ромбе DFS от вершины 0 может найти путь до 2 длиной 3 (0 → 1 → 3 → 2), хотя прямой путь 0 → 2 имеет длину 1. DFS не стремится к кратчайшим путям — он стремится к полному обходу. Именно поэтому для задач поиска кратчайшего пути используют BFS (в невзвешенном графе), а для задач проверки связности, поиска циклов, топологической сортировки — DFS. Выбор обхода определяется задачей, а не тем, какой из них «лучше».

Мы уже разбирали backtracking в уроке 3.5. Backtracking тоже исследует варианты в глубину. Разница здесь в задаче и состоянии: обходим ли мы каждую вершину один раз или перебираем разные пути и решения.

В backtracking мы строим решение: пробуем вариант, углубляемся, а если он не подошёл, отменяем выбор и пробуем следующий. Состояние при этом восстанавливается: мы снимаем флаг used, возвращаем элемент из пути. Это отмена выбора, потому что разные ветви перебора должны начинаться с одного и того же состояния.

В DFS мы обходим граф и не отменяем посещение. Однажды пометив вершину visited, мы оставляем её посещённой навсегда — до конца всего обхода. Снимать visited было бы ошибкой: тогда одна и та же вершина могла бы быть обработана много раз, и обход потерял бы линейность. Если сохранять пометки лишь на текущем пути и снимать их при возврате, перебор простых путей остаётся конечным, но может повторно обрабатывать вершины огромное число раз. Бесконечное хождение возможно при отсутствии защиты от повторов даже на текущем пути.

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

Трасса на ромбе

Возьмём тот же граф, что и в BFS: рёбра (0, 1), (0, 2), (1, 3), (2, 3), (3, 4), плюс изолированная вершина 5. Соседи добавляются в порядке возрастания: у 0 соседи 1, 2; у 1 соседи 0, 3; у 2 соседи 0, 3; у 3 соседи 1, 2, 4; у 4 сосед 3.

Запускаем рекурсивный DFS из 0. Посещаем 0, записываем в pre-order. Перебираем соседей 0: первый — 1. Не посещён, спускаемся в 1. Посещаем 1, записываем. Соседи 1: 0 — посещён, пропускаем; 3 — не посещён, спускаемся. Посещаем 3, записываем. Соседи 3: 1 — посещён, 2 — не посещён, спускаемся. Посещаем 2, записываем. Соседи 2: 0 — посещён, 3 — посещён. Записываем 2 в post-order и возвращаемся к 3. У 3 следующий сосед после 2 — 4, не посещён, спускаемся. Посещаем 4, записываем. Соседи 4: 3 — посещён. Записываем 4 в post-order и возвращаемся к 3. У 3 больше нет непосещённых соседей. Записываем 3 в post-order. Возвращаемся к 1. У 1 больше нет непосещённых соседей. Записываем 1 в post-order. Возвращаемся к 0. У 0 остался сосед 2, но он уже посещён. Записываем 0 в post-order.

Итог: pre-order = [0, 1, 3, 2, 4], post-order = [2, 4, 3, 1, 0].

Обратите внимание: DFS-путь до 2 оказался 0 → 1 → 3 → 2, длина 3, хотя прямой путь 0 → 2 имеет длину 1. Это и есть та самая некратчайшесть, о которой мы говорили. DFS не обязан находить короткие пути: он идёт по первому непосещённому соседу, а не ищет минимальный.

Программа: рекурсия и явный стек

Соберём DFS в двух вариантах. Вход — корректный список смежности: каждый список существует, номера соседей лежат в 0..V−1, граф не меняется во время обхода. Рекурсивный — самый естественный: функция вызывает саму себя для каждого непосещённого соседа. Итеративный с явным стеком — чтобы показать, что рекурсия не обязательна, и что тот же порядок можно получить, эмулируя стек кадров вручную.

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

using System;
using System.Collections.Generic;

int V = 6;
var adj = new List<int>[V];
for (int i = 0; i < V; i++) adj[i] = new List<int>();
AddEdge(adj, 0, 1);
AddEdge(adj, 0, 2);
AddEdge(adj, 1, 3);
AddEdge(adj, 2, 3);
AddEdge(adj, 3, 4);

var (pre1, post1) = DfsRecursive(adj, 0);
Console.WriteLine(string.Join(" ", pre1));
Console.WriteLine(string.Join(" ", post1));

var (pre2, post2) = DfsIterativeFrames(adj, 0);
Console.WriteLine(string.Join(" ", pre2));
Console.WriteLine(string.Join(" ", post2));

(int[] Pre, int[] Post) DfsRecursive(List<int>[] adj, int start)
{
    if (adj == null) throw new ArgumentNullException(nameof(adj));
    int n = adj.Length;
    if (start < 0 || start >= n) throw new ArgumentOutOfRangeException(nameof(start));

    bool[] visited = new bool[n];
    var pre = new List<int>();
    var post = new List<int>();
    DfsVisit(adj, start, visited, pre, post);
    return (pre.ToArray(), post.ToArray());
}

void DfsVisit(List<int>[] adj, int u, bool[] visited, List<int> pre, List<int> post)
{
    visited[u] = true;
    pre.Add(u);
    foreach (int v in adj[u])
    {
        if (!visited[v])
        {
            DfsVisit(adj, v, visited, pre, post);
        }
    }
    post.Add(u);
}

(int[] Pre, int[] Post) DfsIterativeFrames(List<int>[] adj, int start)
{
    if (adj == null) throw new ArgumentNullException(nameof(adj));
    int n = adj.Length;
    if (start < 0 || start >= n) throw new ArgumentOutOfRangeException(nameof(start));

    bool[] visited = new bool[n];
    var pre = new List<int>();
    var post = new List<int>();
    var stack = new Stack<(int Vertex, int NextNeighbor)>();

    visited[start] = true;
    pre.Add(start);
    stack.Push((start, 0));

    while (stack.Count > 0)
    {
        var (u, idx) = stack.Pop();
        if (idx < adj[u].Count)
        {
            stack.Push((u, idx + 1));
            int v = adj[u][idx];
            if (!visited[v])
            {
                visited[v] = true;
                pre.Add(v);
                stack.Push((v, 0));
            }
        }
        else
        {
            post.Add(u);
        }
    }
    return (pre.ToArray(), post.ToArray());
}

void AddEdge(List<int>[] adj, int u, int v)
{
    adj[u].Add(v);
    adj[v].Add(u);
}

Вывод:

0 1 3 2 4
2 4 3 1 0
0 1 3 2 4
2 4 3 1 0

Обе версии дают одинаковый результат: pre-order 0 1 3 2 4, post-order 2 4 3 1 0. Итеративная версия воспроизводит ту же структуру обхода, что и рекурсивная, потому что мы эмулируем ровно те же кадры.

Разберём, как работает итеративная версия. Стек содержит пары: вершина и номер следующего соседа, который надо рассмотреть. Когда мы извлекаем кадр, смотрим: если ещё остались соседи, кладём кадр обратно с увеличенным номером, а затем проверяем соседа. Если сосед не посещён, помечаем его, добавляем в pre-order и кладём новый кадр для него с нулевым номером. Если соседи кончились, добавляем вершину в post-order и не кладём кадр обратно. Так мы в точности повторяем поведение рекурсии.

Стоит заметить, чего мы не делаем: мы не кладём в стек сразу всех соседей вершины с обещанием, что получится тот же обход. Без дополнительных правил это может изменить порядок и дерево обхода. Кадры с номером следующего соседа прямо воспроизводят рекурсивные входы и выходы; именно этот вариант мы выбрали.

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

Отдельно про глубину рекурсии. Рекурсивный DFS может уйти на глубину V, и для больших графов это может переполнить стек вызовов среды выполнения. Итеративная версия с явным стеком этого недостатка лишена: стек живёт в управляемой памяти, и его размер ограничен только доступной памятью. Поэтому для больших графов итеративный вариант часто предпочтительнее, даже если рекурсивный короче. Мы не будем углубляться в детали того, как устроен стек вызовов, — это уже разбиралось в блоке про рекурсию.

В нашем примере после обхода из 0 вершина 5 осталась непосещённой: она изолирована. Чтобы обойти весь граф, нужен внешний цикл: запускаем DFS из каждой ещё непосещённой вершины, сохраняя общий массив visited между запусками. Тогда после первой компоненты (0, 1, 2, 3, 4) внешний цикл дойдёт до 5 и запустит DFS из неё, добавив её в pre и post. Такой приём мы будем использовать, когда речь пойдёт о компонентах связности.

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

Для ненаправленного графа ситуация проще. Здесь ребро, ведущее обратно к родителю, — не цикл: это просто то же самое ребро, по которому мы пришли. Настоящий цикл в ненаправленном графе — это когда мы наткнулись на уже посещённую вершину, которая не является нашим родителем. Об этом мы поговорим подробнее, когда будем разбирать обнаружение циклов. Сейчас нам важно запомнить: visited — необходимое, но не достаточное условие для анализа циклов, и в следующих уроках мы это уточним.

Мы разобрали оба обхода, и полезно сравнить их по назначению. BFS находит кратчайшие пути по числу рёбер в невзвешенном графе. DFS этого не делает, но зато естественно подходит для задач, где нужно углубиться в структуру: проверить связность, найти цикл, построить топологический порядок, найти компоненты сильной связности. DFS не быстрее BFS и не медленнее: у них одинаковая сложность O(V + E). Разница только в порядке обхода, и этот порядок определяет, какие задачи решаются удобно, а какие — нет. Выбор диктуется задачей, а не скоростью.