Информатика / Алгоритмы и анализ данных

Поиск в глубину: дерево обхода и времена входа и выхода

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

Опубликовано: 21 октября 2026 г.Обновлено: 21 октября 2026 г.

Формула

u\text{ — предок }v\iff t_{in}(u)<t_{in}(v)<t_{out}(v)<t_{out}(u),\quad u\ne v

Схема Лес DFS: A → B → D → C

AB, BD, DC — дерево; E — отдельная компонента

Обозначения

$u,v$: две различные вершины леса обхода, не применяется
$t_{in}(v)$: номер события первого входа в вершину, целый счётчик
$t_{out}(v)$: номер события завершения обработки вершины, целый счётчик
$V,E$: множества вершин и рёбер исходного графа, не применяется

Условия применения

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

Ограничения

Порядок обхода зависит от порядка соседей и стартовых вершин. Найденный путь обычно не является кратчайшим. Глубина рекурсии может достигать числа вершин; для большого графа нужен явный стек с сохранением позиции в списке соседей. Проверка интервалов говорит о дереве обхода, а не обо всех путях исходного графа.

Подробное объяснение

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

Событие входа в предка происходит раньше входа в потомка, а выход из предка — позже выхода из потомка. Получаются вложенные интервалы. У вершин из разных уже завершённых ветвей интервалы не пересекаются. Это свойство позволяет после обхода отвечать на вопрос о строгом предке четырьмя сравнениями чисел.

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

На списках смежности каждая вершина открывается один раз, а каждая запись ребра рассматривается один раз. Для неориентированного ребра таких записей две, что не меняет итоговую оценку O(|V|+|E|). При матрице смежности просмотр всех возможных соседей может потребовать O(|V|²).

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

Как пользоваться формулой

Задайте порядок стартовых вершин и соседей; пометьте все вершины непосещёнными и обнулите общий счётчик событий.
При первом входе пометьте вершину, увеличьте счётчик и сохраните время входа до перехода к её непосещённым соседям.
После завершения всех соседей увеличьте счётчик ещё раз и запишите время выхода, затем вернитесь к родителю.
Для двух разных вершин сравните интервалы входа и выхода; отдельно проверьте, что речь идёт о родстве в лесу обхода.

Историческая справка

В теории алгоритмов поиск в глубину стал основой линейных методов анализа структуры графа. Статья Роберта Тарьяна «Depth-First Search and Linear Graph Algorithms», опубликованная в 1972 году, рассматривает сильные и двусвязные компоненты через свойства такого обхода. Эта работа показывает значение дерева поиска для более сложных задач, но не требует приписывать Тарьяну любое использование обхода с возвратом. В курсе MIT 6.006 2011 года DFS и топологическая сортировка рассматриваются вместе: порядок открытия и завершения вершин помогает перейти от простой достижимости к зависимостям. Современные учебные реализации явно хранят метки посещения и служебные счётчики; времена входа и выхода дают компактное представление вложенности вызовов.

Историческая линия формулы

DFS — общепринятое название стратегии обхода с углублением и возвратом. Работа Тарьяна 1972 года служит историческим источником по линейным графовым алгоритмам на основе DFS. Она не используется как доказательство единоличного изобретения всей стратегии поиска в глубину.

Пример

Рассмотрим неориентированный граф с рёбрами AB, AC, BD, CD и изолированной вершиной E. Стартуем с A, соседей читаем по алфавиту, счётчик событий начинается с 1. Получаем входы A = 1, B = 2, D = 3, C = 4, затем выходы C = 5, D = 6, B = 7, A = 8. Для E остаются вход 9 и выход 10. Дерево первой компоненты содержит AB, BD, DC; ребро AC в дерево не входит. У B интервал [2,7], у C — [4,5], поэтому B является предком C в этом дереве. В исходном графе при этом есть прямое ребро AC: дерево не перечисляет все возможные пути. Из A достижимы четыре вершины; весь лес содержит две компоненты.

Частая ошибка

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

Практика

Задачи с решением

Предок по интервалам

Условие. У u времена [3,12], у v — [6,9], у w — [13,16]. Кто из v и w является потомком u?

Решение. Для v верно 3 < 6 < 9 < 12. Интервал w начинается после выхода из u, поэтому вложенности нет.

Ответ. v — потомок u; w — нет.

DFS и длина пути

Условие. В графе AB, BC, CD, AD старт A, соседи по алфавиту. Какой путь дерево DFS даёт до D и кратчайший ли он?

Решение. Обход углубляется A→B→C→D. Путь в дереве содержит 3 ребра, но в графе есть ребро AD и путь длины 1.

Ответ. Дерево даёт длину 3; кратчайшая длина равна 1.

Дополнительные источники

https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/lecture-14-depth-first-search-dfs-topological-sort/
https://algs4.cs.princeton.edu/41graph/DepthFirstSearch.java.html
https://www.cs.cmu.edu/~cdm/resources/Tarjan1972-sccs.pdf

Связанные формулы

Информатика

Топологическая сортировка Кана по входящим степеням

$d_{in}(v)\leftarrow d_{in}(v)-1\quad\text{при удалении дуги }u\to v;\qquad |L|=|V|\iff G\text{ ацикличен}$

Алгоритм Кана упорядочивает вершины ориентированного графа, последовательно выбирая вершину без входящих дуг. Если вывести все вершины не удалось, оставшаяся часть содержит ориентированный цикл.

Информатика

Сильные компоненты: два обхода алгоритма Косарайю

$u\sim v\iff(u\leadsto v)\land(v\leadsto u),\qquad T=O(|V|+|E|)$

Сильная компонента ориентированного графа объединяет вершины, достижимые друг из друга в обоих направлениях. Алгоритм Косарайю находит такие группы двумя обходами в глубину с разворотом всех дуг.

Информатика

Мосты графа: критерий через времена входа и low

$(v,u)\text{ — мост}\iff low(u)>t_{in}(v),\quad u\text{ — ребёнок }v\text{ в DFS}$

Мост — ребро неориентированного графа, удаление которого увеличивает число компонент связности. DFS обнаруживает его, если поддерево ребёнка не имеет обходного ребра к родителю или его предкам.

Информатика

Точки сочленения: критерий low и отдельное правило корня

$v\ne root:\quad v\text{ — точка сочленения}\iff\exists u\text{ — ребёнок}:low(u)\ge t_{in}(v)$

Точка сочленения — вершина, удаление которой вместе с инцидентными рёбрами увеличивает число компонент связности. Для некорневой вершины DFS использует нестрогое сравнение low ребёнка с временем входа.