Поиск в глубину
Также: Depth-first search · DFS · обход в глубину · метод Тремо
Обход, который идёт вперёд до упора и возвращается только из тупика. Кратчайших путей он не ищет, зато ставит каждой вершине время входа и выхода, и по этим двум числам видно всё устройство графа: циклы, порядок зависимостей, мосты.
В JavaScript этого сайта на 10 октября 2026 года было 1260 модулей и 2929 импортов. Если модуль A импортирует B, а B через цепочку импортов — снова A, браузеру приходится выполнить один из них раньше другого, и тот увидит соседа недоделанным. Есть ли на сайте такой круг? Чтобы ответить, хватит одного прохода поиска в глубину по всем импортам. Ниже — 20 модулей движка символьной математики, на котором работают решатели и тренажёры «Царицы наук», и поиск по их 98 импортам, шаг за шагом.
Каждый модуль — полоса от момента, когда поиск в него вошёл, до момента, когда вышел. Полосы вкладываются друг в друга, как скобки, — почему так всегда, доказано ниже. Из 98 импортов 19 ведут по дереву поиска, 6 — к потомкам, которых уже нашли другой дорогой, 72 — в ветки, закрытые раньше, и только один ведёт вверх, к модулю, который ещё на стеке: poly.js импортирует expand.js, а expand.js — poly.js. Это единственный цикл на всём сайте — по крайней мере на день снимка. Переключите проверку на «уже видели»: наивное правило «пришли туда, где были, — значит круг» поднимет 79 тревог вместо одной.
Идея
Идите по рёбрам вперёд, пока есть куда, а в тупике возвращайтесь на шаг назад и пробуйте следующее ребро. Путь от начала до текущей вершины — это стек: шаг вперёд кладёт вершину, возврат её снимает. Отметьте для каждой вершины два момента — когда вошли и когда вышли. Вершины, в которые вошли и ещё не вышли, — ровно стек, и ребро в такую вершину означает цикл.
Отметки удобно считать одними часами: каждый вход и каждый выход сдвигает их на единицу. Эти два числа называют временем входа и выхода. Вместе с ними вершина проходит три состояния: белая — ещё не видели, серая — вошли, но не вышли, чёрная — вышли. Серые вершины в любой момент образуют путь от корня поиска до текущей вершины.
Каждое ребро u → v поиск рассматривает ровно один раз, стоя в u, и по цвету v в этот момент ребро попадает в один из четырёх классов:
- по дереву — v белая, поиск уходит в неё; эти рёбра образуют дерево (или лес) поиска;
- обратное — v серая, то есть это предок u на стеке; ребро замыкает цикл;
- прямое — v чёрная и вошли в неё позже, чем в u: это потомок, до которого дошли раньше по другой дороге;
- перекрёстное — v чёрная и вошли в неё раньше u: она в другой, уже закрытой ветке.
На полосах классы видны глазами. Обратное ребро бьёт вертикально вверх, в полосу, которая ещё открыта. Прямое уходит вниз и влево, внутрь собственной полосы u. Перекрёстное упирается в полосу, которая закрылась до того, как открылась полоса u.
Почему по скобкам видно всё
Для любых двух вершин u и v отрезки [tin, tout] либо не пересекаются, либо один целиком лежит внутри другого. Отрезок v лежит внутри отрезка u тогда и только тогда, когда v — потомок u в дереве поиска.
Пусть tin[u] < tin[v]. Если в момент входа в v вершина u уже чёрная, то tout[u] < tin[v], и отрезки не пересекаются. Если серая, то u лежит на стеке, и v положили выше неё, то есть v — потомок u. Стек снимается сверху, поэтому из v выйдут раньше, чем из u: tout[v] < tout[u], и отрезок v внутри отрезка u.
Если записать вход в вершину открывающей скобкой, а выход — закрывающей, получится правильная скобочная запись. Под сценой она выписана целиком: (index (rational) (ast) …). Вторая теорема говорит, кто окажется потомком.
Вершина v станет потомком u тогда и только тогда, когда в момент входа в u из u в v ведёт путь только по белым вершинам.
Если v — потомок, путь по дереву от u к v в момент входа в u белый: в его вершины войдут позже. Обратно: пусть белый путь есть, а v не стала потомком. Возьмём на пути первую вершину w, которая не стала потомком; её предшественник p на пути — потомок u (или сама u). Поиск не выйдет из p, не рассмотрев ребро p → w, а к этому моменту w либо уже найдена внутри отрезка u, либо будет найдена прямо сейчас. В обоих случаях w — потомок. Противоречие.
В ориентированном графе есть цикл тогда и только тогда, когда поиск в глубину находит хотя бы одно обратное ребро.
Обратное ребро u → v ведёт в предка: от v по дереву можно дойти до u, и ребро замыкает круг. Обратно: пусть цикл есть, и v — первая вершина цикла, в которую вошёл поиск. В этот момент остальные вершины цикла белые, и путь по циклу от v до её предшественницы u на цикле белый. По лемме u станет потомком v, и когда поиск рассмотрит ребро u → v, вершина v будет ещё серой.
Отсюда и цена наивной проверки. Чёрная вершина — не цикл: в неё просто ведут два пути, как в ромбе, где два модуля импортируют один и тот же третий. В коде сайта таких рёбер тысячи. Цикл выдают только серые вершины.
Код
Рекурсивная версия почти дословно повторяет определение. Цвет хранит словарь, часы — одна переменная. Демо — семь модулей того же движка и импорты между ними:
Последняя строка — модули в порядке времени выхода. Именно так их выполнит браузер, если страница загрузит solve.js: модуль запускается после всех, кого он импортирует. Видно и цену цикла: poly.js выполнится раньше expand.js, хотя импортирует его. Объявления функций из expand.js ему уже доступны, а вот константы и классы, которые expand.js ещё не успел создать, на этот момент недоступны, и обращение к ним при загрузке poly.js кончилось бы ошибкой ReferenceError.
На больших графах рекурсию заменяют своим стеком. Но в стеке нужно хранить не вершины, а пары «вершина и место, где мы остановились в её списке соседей»: это и есть кадр стека вызовов. В Python место хранит итератор, в Go — номер следующего соседа. Программа ниже проходит все модули сайта, считает классы рёбер и печатает найденный цикл — серая часть стека от вершины, в которую упёрлось обратное ребро:
Стек ни разу не стал глубже семи модулей: код сайта неглубокий. Поиск оставил 763 ребра в дереве, 2093 перекрёстных, 72 прямых и одно обратное. Наивная проверка подняла бы 2166 тревог.
Ловушка: стек вершин — не поиск в глубину
Часто пишут так: достать вершину из стека, положить в стек всех её непомеченных соседей и сразу пометить их. Цикл короткий и похож на поиск в глубину, но им не является. Соседей кладут в стек все сразу, поэтому сосед, отложенный давно, достанется позже, чем вершины, до которых дошли через его братьев. Обходит такой цикл те же вершины, но порядок у него другой, и времени выхода у вершин нет вовсе: вершину снимают со стека раньше, чем разберут её потомков.
Пока нужно только «что достижимо», это не важно. Когда нужен порядок, это ошибка. По спецификации ECMAScript браузер выполняет модуль после модулей, которые тот импортирует, в порядке строк import — это порядок выхода поиска в глубину. Ниже рядом настоящий поиск и стек вершин, у которого порядок взят задом наперёд:
У настоящего поиска нарушено только одно ребро — то, что внутри цикла poly ↔ expand, без него не обойтись при любом порядке. Стек вершин при загрузке solve.js нарушает ещё два импорта: simplify.js выполнился бы раньше evaluate.js, а poly.js — раньше numeric.js, хотя оба импортируют их. Выберите index.js — нарушений станет семь.
Правильная итеративная версия хранит в стеке кадры: вершину и номер следующего соседа (или итератор). Тогда стек в каждый момент совпадает со стеком рекурсии, у вершин есть время выхода, и на нём работают все теоремы этой статьи.
Сколько это стоит
Каждая вершина входит в стек и выходит из него один раз, каждое ребро рассматривается один раз — из своего начала. Итого O(V + E) времени и O(V) памяти на цвета, отметки и стек. Для всего сайта это 1260 входов, 1260 выходов и 2929 рёбер — доли миллисекунды.
Подвох — в глубине. Стек может вырасти до V: на цепочке из ста тысяч модулей рекурсия уйдёт на сто тысяч уровней. В Python предел глубины по умолчанию — тысяча вызовов. Его поднимают sys.setrecursionlimit, и с версии 3.11 вызовы Python-функций не расходуют стек процессора, поэтому глубокая рекурсия больше не роняет интерпретатор. В песочнице этой статьи рекурсия глубиной 200 000 отработала, а на миллионе уровней программа упёрлась в предел памяти 256 МБ. В Go стек горутины растёт сам, по умолчанию до 1 ГБ: в песочнице прошла рекурсия на миллион уровней, а на десяти миллионах снова кончилась память. Свой стек кадров снимает вопрос совсем — он лежит в обычной памяти и растёт, пока есть место.
Где работает
Порядок и циклы зависимостей. Поиск в глубину лежит под топологической сортировкой: порядок выхода, прочитанный задом наперёд, — правильный порядок зависимостей. Go запрещает циклические импорты пакетов: go build отказывается собирать программу и печатает import cycle not allowed вместе с самим кругом. Браузер циклы разрешает, но платит тем, что один модуль цикла видит другой недоделанным.
Структура графа. Разметка временем входа и выхода — основа целой семьи линейных алгоритмов: компоненты сильной связности Тарьяна и Косараю, мосты и точки сочленения, проверка планарности. Все они — один проход поиска в глубину с парой чисел на вершину.
Перебор с возвратом. Судоку, расстановки ферзей, решатели логических формул — это поиск в глубину по дереву частичных решений, которое нигде не хранится целиком: шаг вперёд — следующее решение, тупик — откат. Подробнее — перебор с возвратом.
Лабиринты. Поиск в глубину со случайным выбором соседа строит лабиринт без петель, а правила выхода из лабиринта, которые Эдуард Люка в 1882 году приписал телеграфному инженеру Тремо, — тот же поиск в глубину, записанный мелом на стенах. Об этом подробно в главе курса о графах.
Тарьян и Хопкрофт
Обходить лабиринт с возвратами умели давно, но как инструмент для алгоритмов поиск в глубину открыли в начале 1970-х. Роберт Тарьян писал диссертацию о проверке планарности — можно ли нарисовать граф на плоскости без пересечений рёбер — и защитил её в 1972 году. В том же году вышла его статья «Depth-first search and linear graph algorithms»: поиск в глубину с временами входа давал в ней за линейное время компоненты сильной связности и двусвязные компоненты. В 1974 году Тарьян и Джон Хопкрофт опубликовали первую проверку планарности за линейное время — тоже на поиске в глубину. В 1986 году оба получили премию Тьюринга «за фундаментальные достижения в построении и анализе алгоритмов и структур данных».
Его брат — поиск в ширину: тот же обход с очередью вместо стека. Волна находит кратчайшие пути, но не знает, где кончается ветка, и поэтому не видит ни циклов, ни порядка.
Задачи
Обе задачи — на настоящих импортах этого сайта. В первой нужно отличить цикл от ромба. Во второй — повторить браузер: напечатать модули в порядке выполнения, и стек вершин здесь не поможет.
Цикл импортов Порядок выполнения модулейДанные: Импорты JavaScript legost.in