Обход в глубину в графе: одна пометка меняет всё

Если ты уверенно пишешь DFS по спискам смежности с пометками, знаешь, почему он стоит O(V + E), и помнишь про запуск из каждой непосещённой вершины, листай до «Теперь сам».

Как думаешь, что сломается без пометок

Возьми треугольник: вершины a, b, c, соединённые попарно. Запусти в уме обычный обход дерева: из a идём в b, из b - в c, из c - в a, из a - в b... Прежде чем читать дальше, ответь на два вопроса. Первый: когда этот обход закончится? Второй, менее очевидный: а если циклов в графе нет - скажем, это ориентированный граф зависимостей, - нужны ли пометки вообще?

На что это похоже

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

Механизм: рекурсия плюс массив пометок

visited = [False] * V

def dfs(v):
    visited[v] = True          # ПОМЕТКА СТАВИТСЯ ПРИ ВХОДЕ, до перебора соседей
    for u in adj[v]:
        if not visited[u]:
            dfs(u)

# у графа нет корня: запускаем из каждой непосещённой вершины
components = 0
for v in range(V):
    if not visited[v]:
        components += 1
        dfs(v)

Три места, каждое из которых важно.

Пометка при ВХОДЕ, а не при выходе. Если поставить visited[v] = True после перебора соседей, вершина останется непомеченной на всё время своего обхода, и цикл вернёт нас в неё снова - рекурсия уйдёт в бесконечность. Это та самая ошибка, ради которой написан весь урок.

Проверка перед спуском. Условие if not visited[u] стоит ДО вызова; проверять внутри dfs тоже можно, но тогда в стек успевают попасть лишние вызовы.

Внешний цикл по всем вершинам. Обход из одной вершины найдёт только её компоненту связности. Счётчик запусков внешнего цикла - это и есть число компонент; так задача «сколько кусков в графе» решается одной строкой поверх обхода.

Правило

Обход в глубину в графе - это обход дерева плюс массив visited: пометка ставится при ВХОДЕ в вершину, и в помеченную вершину не спускаются. Цена - O(V + E): каждая вершина раскрывается ровно один раз, а суммарная длина всех списков смежности равна 2E в неориентированном графе и E в ориентированном. У графа нет корня, поэтому обход запускают из каждой непосещённой вершины; число запусков равно числу компонент связности.

Разбор: почему обход стоит ровно O(V + E)

Оценка складывается из двух независимых слагаемых, и полезно понимать, откуда каждое.

Первое: O(V). Тело dfs(v) выполняется не больше одного раза для каждой вершины - за этим следит пометка. Плюс внешний цикл проходит по всем V вершинам, даже по тем, что уже посещены.

Второе: O(E). Внутри dfs(v) мы перебираем список соседей, а это deg(v) шагов. Суммируем по всем вершинам: Σ deg(v) = 2E в неориентированном графе (каждое ребро лежит в двух списках) и Σ deg⁺(v) = E в ориентированном. Заметь важное: ребро просматривается даже тогда, когда по нему НЕ идут - проверка visited[u] тоже стоит шага. Поэтому в оценке стоит E, а не «число пройденных рёбер».

Вместе - O(V + E), и это линейно от размера входа: граф на списках смежности как раз и занимает V + E ячеек. Линейный обход - нижняя планка, дешевле прочитать граф нельзя. А вот на матрице смежности тот же алгоритм стоил бы O(V²), потому что перебор соседей там - это проход по целой строке. Одна и та же программа, разные представления - разные оценки; в этом и был смысл прошлой главы.

Разбор: нужны ли пометки, если циклов нет

Возвращаемся к вопросу из вступления. Пусть граф ациклический - скажем, «ромбовая цепочка»: s→a₁, s→b₁, a₁→c₁, b₁→c₁, затем c₁→a₂, c₁→b₂, a₂→c₂, b₂→c₂ и так далее, k звеньев. Циклов нет ни одного, рекурсия точно завершится - но без пометок она посетит c₁ ДВАЖДЫ (через a₁ и через b₁), c₂ - четырежды, c₃ - восемь раз: на каждом звене число путей удваивается. К k-му звену обход раскроет вершину 2^k раз, хотя вершин в графе всего 3k + 1.

Значит пометки нужны не только против бесконечности. Они превращают «число ПУТЕЙ» в «число ВЕРШИН»: без них цена обхода равна количеству различных путей из старта, а оно бывает экспоненциальным даже без единого цикла.

Разбор: обходим граф по шагам

Граф: 0-1, 0-2, 1-3, 2-3, 4-5 (неориентированный, шесть вершин). Списки смежности: adj[0] = [1,2], adj[1] = [0,3], adj[2] = [0,3], adj[3] = [1,2], adj[4] = [5], adj[5] = [4].

Внешний цикл, v = 0: не посещена - запускаем dfs(0), компонент стало 1.

1. dfs(0): помечаем 0. Соседи [1, 2]. Первый - 1, не посещён → dfs(1).
2. dfs(1): помечаем 1. Соседи [0, 3]. Ноль уже помечен - пропускаем (ребро посмотрели, но не пошли). Тройка не посещена → dfs(3).
3. dfs(3): помечаем 3. Соседи [1, 2]. Единица помечена - пропуск. Двойка нет → dfs(2).
4. dfs(2): помечаем 2. Соседи [0, 3] - оба помечены. Возврат.
5. Возвращаемся по цепочке: 3 → 1 → 0. Первая компонента обойдена: {0, 1, 2, 3}.

Внешний цикл продолжается: v = 1, 2, 3 - уже посещены, пропускаем. v = 4 - не посещена, компонент стало 2, dfs(4) помечает 4, идёт в 5, возвращается. v = 5 - посещена.

Итог: две компоненты связности, порядок посещения 0, 1, 3, 2, 4, 5. Обрати внимание на порядок: мы ушли «вглубь» до конца (0→1→3→2), прежде чем вернуться, - отсюда и название. И заметь, что порядок зависит от порядка соседей в списках: начни adj[0] с двойки, и обход пойдёт 0, 2, 3, 1. Обход в глубину не единственный - он определён с точностью до порядка списков.

Что ломается без этого

Первое и главное: пометка при выходе вместо входа - бесконечная рекурсия на первом же цикле. Второе: забыть внешний цикл и обойти только одну компоненту; на связном тестовом графе всё работает, а на реальных данных половина вершин остаётся необработанной. Третье: ждать от обхода в глубину кратчайших путей. Он находит ПУТЬ, а не кратчайший: в разобранном примере до вершины 2 он дошёл за три шага (0→1→3→2), хотя есть прямое ребро 0-2. Кратчайшие пути в невзвешенном графе даёт обход в ШИРИНУ. Четвёртое: рекурсия на большом графе - глубина рекурсии доходит до V, и на цепочке из миллиона вершин программа падает по переполнению стека (об этом отдельный урок). Пятое: держать пометки в словаре вместо массива, когда вершины пронумерованы, - работает, но в разы медленнее, а на больших графах это заметно.

Зачем это в работе

Обход в глубину - не «один из алгоритмов», а каркас, на котором держится почти всё остальное в этом разделе: топологическая сортировка, компоненты сильной связности, мосты и точки сочленения, проверка двудольности - это DFS плюс немного бухгалтерии по дороге. Отдельно он решает: поиск циклов (в зависимостях пакетов, в блокировках базы, в конфигурации), проверку достижимости («может ли этот код вообще выполниться»), заливку области в редакторе изображений, обход дерева каталогов, фазу пометки в сборщике мусора (он буквально помечает достижимые объекты), разбор выражений и обход синтаксических деревьев в компиляторах. Общая примета задачи: «дойти до всего, что достижимо, и что-то по дороге посчитать». А O(V + E) означает, что стоимость - это стоимость чтения графа: дешевле не бывает.

Теперь сам

Ориентированный граф: 0→1, 1→2, 2→0, 3→1. Сколько раз выполнится тело dfs, если запустить обход с внешним циклом по вершинам 0, 1, 2, 3? Сколько рёбер будет просмотрено?