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

Обход графа в глубину (depth-first search, DFS) перебирает вершины по принципу «иди, пока идётся»: из текущей вершины алгоритм уходит по первому же непройденному ребру как можно дальше и пятится назад только тогда, когда впереди всё уже посещено. Из этой простой дисциплины вырастают почти все структурные алгоритмы на графах: проверка ацикличности, поиск компонент, мосты и точки сочленения, сильно связные компоненты. Разберём обход на одном конкретном графе из восьми вершин и девяти рёбер, а в калькуляторе ниже прокрутите ту же трассировку по шагам.

Что делает обход графа в глубину

Граф задан списками смежности, соседи в каждом списке перебираются по алфавиту:

A: B, D     E: D, F
B: C        F: E
C: D        G: H
D: B

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

Из вершины $A$ алгоритм спускается по цепочке $A \to B \to C \to D$ и только там упирается: единственный сосед вершины $D$ это $B$, а она уже серая. Вершины закрываются в обратном порядке: $D$, $C$, $B$, $A$. Ключевая особенность обхода в глубину в том, что он не идёт «кольцами» вокруг стартовой вершины, как обход в ширину, а сразу проваливается в одну ветку до упора. Именно поэтому он даёт информацию о структуре графа, а не о расстояниях.

Одного запуска почти никогда не хватает: из $A$ недостижимы ни $E$, ни $G$. Поэтому снаружи стоит цикл по всем вершинам, который запускает обход из каждой ещё не найденной. В нашем графе он сработает трижды, и получится лес обхода в глубину из трёх деревьев с корнями $A$, $E$, $G$.

Рекурсия и явный стек: две записи одного алгоритма

Рекурсивная запись занимает шесть строк:

dfs(u):
    color[u] = серый
    for w in adj[u]:
        if color[w] == белый:
            dfs(w)
    color[u] = чёрный

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

Рассчитать для своей задачи

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

Три цвета вершин, время входа и время выхода

Стандартная реализация хранит для каждой вершины цвет и две метки времени. Белая вершина ещё не найдена, серая найдена, но её обход не завершён (она лежит в стеке), чёрная завершена полностью. Счётчик времени увеличивается на единицу при каждом событии: $t_{in}(v)$ ставится при входе, $t_{out}(v)$ при выходе. Всего событий ровно $2V$, поэтому в нашем графе время пробегает значения от 1 до 16.

Рассчитать для своей задачи

Интервалы $[t_{in}(v), t_{out}(v)]$ подчиняются теореме о скобках: для любых двух вершин интервалы либо вложены один в другой, либо не пересекаются вовсе. Частичного перекрытия не бывает - ровно как у правильно расставленных скобок. Вложенность означает родство: $D$ с интервалом $(4, 5)$ лежит внутри $C$ с интервалом $(3, 6)$, значит $D$ - потомок $C$ в дереве обхода. Непересекающиеся интервалы $A$ $(1, 8)$ и $E$ $(9, 12)$ говорят, что вершины лежат в разных ветвях или даже в разных деревьях леса.

Из длины интервала бесплатно получается размер поддерева:

$|T_v| = \frac{t_{out}(v) - t_{in}(v) + 1}{2}$

Для корня $A$ это $(8 - 1 + 1)/2 = 4$ вершины, и действительно его поддерево - это $A$, $B$, $C$, $D$. Проверка «является ли $u$ предком $v$» тоже сводится к одному сравнению: $t_{in}(u) < t_{in}(v)$ и $t_{out}(v) < t_{out}(u)$. На этом приёме держатся запросы к деревьям и методы вроде разбиения на цепочки.

Четыре класса рёбер

Обход в глубину раскладывает все рёбра ориентированного графа на четыре класса. Класс определяется цветом конца ребра в момент, когда алгоритм его рассматривает.

Рассчитать для своей задачи

• Древесное: конец белый, по этому ребру обход и уходит вглубь. Таких рёбер ровно $V$ минус число деревьев леса, у нас $8 - 3 = 5$.
• Обратное: конец серый, то есть ребро ведёт в предка, который ещё не завершён. У нас это $D \to B$ и $F \to E$.
• Прямое: конец чёрный и является потомком текущей вершины ($t_{in}(u) < t_{in}(w)$). Ребро $A \to D$ ведёт к уже завершённому потомку.
• Перекрёстное: конец чёрный, но лежит в другой ветке или другом дереве ($t_{in}(u) > t_{in}(w)$). Ребро $E \to D$ уходит в уже закрытое первое дерево.

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

Поиск цикла и компоненты связности

Из классификации сразу следуют два самых частых применения обхода. Третье применение выносится в отдельную задачу: если граф ациклический, порядок выхода из вершин, развёрнутый задом наперёд, даёт топологическую сортировку.

Цикл. Ориентированный граф ацикличен тогда и только тогда, когда обход в глубину не нашёл ни одного обратного ребра. Доказательство в одну сторону очевидно: обратное ребро $u \to w$ вместе с путём из $w$ в $u$ по древесным рёбрам замыкает цикл. В обратную сторону: если цикл есть, то первая вершина цикла, в которую зашёл обход, остаётся серой, пока обход не вернётся к ней по циклу, и ребро в неё окажется обратным. В нашем графе обратных рёбер два, и один из циклов читается прямо со схемы: $B \to C \to D \to B$. Чтобы выписать сам цикл, достаточно запомнить массив предков и подняться по нему от $u$ до $w$.

Компоненты. В неориентированном графе каждый запуск обхода из внешнего цикла накрывает ровно одну компоненту связности, поэтому число компонент равно числу запусков. В нашем графе их две: $\{A, B, C, D, E, F\}$ и $\{G, H\}$. В ориентированном случае число деревьев леса зависит от порядка перебора вершин и компонентой не является: там нужны более тонкие схемы вроде алгоритма Тарьяна для сильно связных компонент, который тоже построен на одном проходе обхода в глубину и на временах входа.

Сложность обхода: почему O(V + E)

Каждая вершина становится серой ровно один раз, значит рекурсивный вызов делается $V$ раз. Ровно та же оценка выходит и у обхода в ширину: отличаются они порядком посещения и памятью, а не асимптотикой. Каждый список смежности просматривается ровно один раз целиком, значит суммарно рассматривается $E$ рёбер (в неориентированном графе каждое ребро попадается дважды, что даёт $2E$ и ту же асимптотику). Итого:

$T(V, E) = O(V + E)$

Для нашего графа это $8 + 9 = 17$ элементарных действий. Оценка линейна именно потому, что граф хранится списками смежности. При хранении матрицей смежности просмотр соседей одной вершины стоит $O(V)$, и обход деградирует до $O(V^2)$. Память под цвета и времена - $O(V)$, плюс до $O(V)$ на стек.

Частые ошибки

• Два цвета вместо трёх. С флагом «посещено» обход всё ещё обойдёт граф, но отличить обратное ребро от прямого или перекрёстного уже не получится, и проверка на цикл сломается: она начнёт находить «цикл» на ациклическом графе $A \to B$, $A \to C$, $B \to C$.
• Пометка при добавлении в стек. В итеративной версии вершину нужно красить в серый при извлечении, иначе она попадёт в стек по каждому входящему ребру и времена собьются.
• Ребро к родителю в неориентированном графе. Его нельзя считать обратным: иначе любое ребро объявит цикл. Пропускают по номеру ребра, а не по имени вершины, иначе кратные рёбра дадут ложный ответ.
• Рекурсия на больших данных. Глубина стека равна длине самого длинного пути в дереве обхода; на цепочке из $10^6$ вершин рекурсия падает. Итеративная версия или увеличенный лимит стека обязательны.
• Вывод о расстояниях. Порядок обхода в глубину ничего не говорит о длине пути: до вершины $D$ алгоритм добрался за три шага, хотя есть прямое ребро $A \to D$. Кратчайшие пути ищут другими алгоритмами, например алгоритмом Дейкстры.

FAQ

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

Единственный ли порядок обхода у графа? Нет. Он зависит от стартовой вершины и от порядка соседей в списках смежности. Времена входа и выхода, число деревьев в лесу и даже классы отдельных рёбер меняются - в калькуляторе выше это видно при смене старта. Неизменным остаётся факт наличия или отсутствия обратных рёбер, то есть ответ про ацикличность.

Зачем нужны времена выхода, если вход уже всё нумерует? Времена выхода несут информацию о завершённости поддерева. Через них проверяется родство вершин, считается размер поддерева и строится порядок, обратный к порядку выхода. На временах выхода держится и разбор орграфа на сильно связные компоненты.

Коротко

Обход графа в глубину идёт по рёбрам вглубь до упора и возвращается по стеку вызовов, храня для каждой вершины цвет и пару меток времени $t_{in}$ и $t_{out}$. Интервалы времени вкладываются друг в друга как скобки, из чего мгновенно читаются родство вершин и размеры поддеревьев. Рёбра распадаются на древесные, обратные, прямые и перекрёстные, причём наличие обратного ребра равносильно наличию цикла, а число запусков внешнего цикла в неориентированном графе равно числу компонент связности. Всё это обходится в $O(V + E)$ при хранении графа списками смежности.