Поиск в глубину (DFS)
Войдите в лабиринт, идите, пока не упретесь в тупик, затем вернитесь к последней развилке и попробуйте следующий путь. Так же поиск в глубину исследует граф. Это один из самых простых алгоритмов на графах, а стек, который он хранит, говорит больше, чем можно ожидать.
Идея
Граф — это множество вершин, соединенных ребрами: комнаты и двери, веб-страницы и ссылки, задачи и задачи, от которых они зависят. Поиск в глубину посещает каждую вершину, достижимую из старта, но в особом порядке: он всегда продолжает с вершины, достигнутой последней. Он хранит стек вершин, внутри которых находится. Новая вершина кладется наверх, а вершина снимается, только когда все вокруг нее исследовано.
Шаг за шагом
Положите старт в стек и дайте ему номер посещения 1. Посмотрите на следующего соседа верхней вершины. Если его еще не видели, дайте ему следующий номер посещения, запомните вершину, из которой его достигли, и положите его на верх стека. Если его уже видели, пропустите его. Когда у верхней вершины не осталось непроверенных соседей, она обработана: снимите ее и продолжайте с вершины под ней. Остановитесь, когда стек опустеет или когда цель будет достигнута.
Пример
Возьмите граф с ребрами A–B, A–C, B–D, C–D, C–E и D–F, начните с A и проверяйте соседей в алфавитном порядке. Из A поиск идет в B, из B в D, из D в C и из C в E, так что стек — A, B, D, C, E. По пути C видит вершину A, которая еще в стеке: ребро C–A замыкает цикл A, B, D, C. У E нет ничего нового, поэтому она обработана, затем C, и поиск возвращается к D, у которой еще есть F. Порядок посещения: A, B, D, C, E, F. С целью E DFS останавливается на пути A → B → D → C → E из четырех ребер, хотя путь A → C → E занимает всего два.
Для чего он нужен
Стек всегда является путем от старта до текущей вершины, поэтому DFS естественно подходит для лабиринтов и головоломок: на этой идее основан поиск с возвратом. В неориентированном графе ребро к вершине, которая еще в стеке, замыкает цикл. В ориентированном графе, если выписать вершины в порядке, обратном порядку их обработки, получится топологический порядок, и задачи окажутся после задач, от которых они зависят. Поиск в глубину также находит компоненты связности, мосты и точки сочленения, а его случайный вариант — классический способ генерировать лабиринты.
История
В XIX веке французский математик Charles Pierre Trémaux описал способ выбраться из любого лабиринта, помечая коридоры, — это поиск в глубину, выполненный мелом. В 1972 и 1973 годах Robert Tarjan и John Hopcroft показали, что DFS решает многие задачи на графах за линейное время, от сильно связных компонент до проверки, можно ли нарисовать граф без пересечений. В 1986 году они получили премию Тьюринга, в том числе за эту работу.
Попробуйте сами
Откройте приложение и нажмите Шаг. Вершина, соседей которой проверяют, выделена, вершины в стеке синие, а обработанные — зеленые, и на каждой стоит номер посещения. Стек показан под графом, от старта до вершины наверху. Следите за строкой состояния, чтобы увидеть ребра, замыкающие цикл, и выберите цель, чтобы увидеть, насколько длинным может оказаться найденный путь по сравнению с поиском в ширину.
Часто задаваемые вопросы
Какова временная сложность DFS?
O(V + E) для V вершин и E ребер: каждая вершина один раз кладется в стек и один раз снимается с него, а каждое ребро проверяется с обоих концов. Нужно O(V) дополнительной памяти для стека и пометок.
Почему DFS использует стек?
Потому что принцип «последним пришел — первым ушел» заставляет поиск продолжать с самой новой вершины и возвращаться к предыдущей. Рекурсия делает то же самое с помощью стека вызовов программы. С очередью вместо стека поиск расходился бы кольцо за кольцом: это поиск в ширину.
Рекурсивный DFS — проблема для больших графов?
Может быть: длинный путь означает глубокую рекурсию, а многие языки ограничивают глубину вызовов. Итеративный вариант с явным стеком обходит это ограничение и посещает вершины в том же порядке.
Где применяется DFS?
Для решения лабиринтов и головоломок поиском с возвратом, поиска циклов, упорядочивания задач по зависимостям (топологическая сортировка), поиска компонент связности и сильно связных компонент, генерации лабиринтов, а также в компиляторах и системах сборки, которые обходят графы зависимостей.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать поиск в глубину