Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин^[1].

Пусть задан граф ${\displaystyle G=(V,E)}$, где ${\displaystyle V}$ — множество вершин графа, ${\displaystyle E}$ — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

1. Пройдём по всем вершинам ${\displaystyle v\in V}$.
   • Если вершина ${\displaystyle v}$ белая, выполним для неё DFS(v).

Процедура DFS (параметр — вершина ${\displaystyle u\in V}$)

1. Перекрашиваем вершину ${\displaystyle u}$ в серый цвет.
2. Для всякой вершины ${\displaystyle w}$, смежной с вершиной ${\displaystyle u}$ и окрашенной в белый цвет, рекурсивно выполняем процедуру DFS(w)^[2].
3. Перекрашиваем вершину ${\displaystyle u}$ в чёрный цвет.

Часто используют двухцветные метки — без серого, на 1-м шаге красят сразу в чёрный цвет.

На больших графах поиск в глубину серьёзно нагружает стек вызовов. Если есть риск переполнения стека, используют нерекурсивные варианты поиска.

Первый вариант, простейший, но дающий немалый объём стека — до |E|.

1. Кладём в стек первую вершину.
2. Пока стек не пуст, берём верхнюю вершину, не извлекая.
   1. Если вершина белая…
      1. Красим в серый цвет.
      2. Кладём в стек всех её белых соседок в порядке, обратном порядку обхода (если таковой важен).
   2. Если вершина серая, красим в чёрный и извлекаем.
   3. Если вершина чёрная, просто извлекаем.

Если хватает двухцветных меток…

1. Кладём в стек первую вершину.
2. Пока стек не пуст, извлекаем верхнюю вершину. Если она белая…
   1. Красим в чёрный цвет.
   2. Кладём в стек всех её белых соседок в порядке, обратном порядку обхода.

Второй вариант: можно представить стек вызова программно: для каждой из серых вершин в стеке будет храниться её номер ${\displaystyle u}$ и номер текущей смежной вершины ${\displaystyle w}$.

Процедура DFS (параметр — вершина ${\displaystyle u\in V}$)

1. Кладём в стек пару ${\displaystyle (u,\varnothing )}$. Перекрашиваем вершину ${\displaystyle u}$ в серый цвет.
2. Пока стек не пуст…
   1. Берём верхнюю пару ${\displaystyle (v,w)}$, не извлекая её из стека.
   2. Находим вершину ${\displaystyle w'}$, смежную с ${\displaystyle v}$ и следующую за ${\displaystyle w}$.
      1. Если таковой нет, извлекаем ${\displaystyle (v,w)}$ из стека, перекрашиваем вершину ${\displaystyle v}$ в чёрный цвет.
      2. В противном случае присваиваем ${\displaystyle w:=w'}$, прямо в стеке.
         • Если к тому же вершина ${\displaystyle w'}$ белая, кладём на стек пару ${\displaystyle (w',\varnothing )}$, перекрашиваем ${\displaystyle w'}$ в серый цвет.

Третий вариант: можно в каждой из «серых» вершин держать текущее ${\displaystyle w}$ и указатель на предыдущую (ту, из которой пришли).

Для каждой из вершин установим два числа — «время» входа ${\displaystyle entry[u]}$ и «время» выхода ${\displaystyle leave[u]}$.

Модифицируем процедуру DFS так.

1. Увеличиваем «текущее время» на 1. ${\displaystyle entry[u]:=t}$.
2. Перекрашиваем вершину ${\displaystyle u}$ в серый цвет.
3. Для всякой вершины ${\displaystyle v}$, смежной с вершиной ${\displaystyle u}$ и окрашенной в белый цвет, выполняем процедуру DFS(v).
4. Перекрашиваем вершину ${\displaystyle u}$ в чёрный цвет.
5. Увеличиваем «текущее время» на 1. ${\displaystyle leave[u]:=t}$.

Считаем, что граф ориентированный. Очевидно, для любой вершины, из которой мы не вышли в момент t, ${\displaystyle entry[u]\leqslant t<leave[u]}$. Также невозможно скрёстное неравенство: ${\displaystyle entry[u]<entry[v]<leave[u]<leave[v]}$. Просматриваемые на шаге 3 дуги u→v могут быть:

• ${\displaystyle entry[u]<t+1\equiv entry[v]<leave[v]<leave[u]}$. В момент выполнения шага 3 (обозначенный как t) вершина v белая. В таком случае мы для вершины v исполняем DFS, а дуга называется дугой дерева поиска.
• ${\displaystyle entry[u]<entry[v]<leave[v]\leqslant t<leave[u]}$. В момент t вершина v чёрная, сравнение entry говорит, что в v попали из u. Такая дуга называется прямой.
• ${\displaystyle entry[v]<leave[v]<entry[u]\leqslant t<leave[u]}$. В момент t вершина v также чёрная, но сравнение entry говорит, что в v попали в обход u. Такая дуга называется перекрёстной.
• ${\displaystyle entry[v]<entry[u]\leqslant t<leave[u]<leave[v]}$. В момент t вершина v серая, то есть в u попали из v. Имеем дело с обратной дугой.

Рёбра неориентированного графа могут быть рёбрами дерева и обратными, но не прямыми и перекрёстными.^[3] Чтобы различать рёбра неориентированного графа, достаточно указанных выше трёх- или двухцветных отметок. Ребро, идущее в белую вершину,— ребро дерева. В серую (чёрную в двухцветном варианте) — обратное. В чёрную — такого не бывает.^[4]

Алгоритм Косарайю требует сортировки вершин в обратном порядке по времени выхода. Метка входа и типы рёбер нужны в алгоритмах поиска точек сочленения и мостов. Метки выхода в обратном порядке — топологический порядок вершин.

Поиск в глубину ограниченно применяется как собственно поиск, чаще всего на древовидных структурах: когда расстояние между точками малó, поиск в глубину может «плутать» где-то далеко.

Зато поиск в глубину — хороший инструмент для исследования топологических свойств графов. Например:

• В качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент.
• В топологической сортировке.
• Для поиска точек сочленения, мостов.
• Для преобразования синтаксического дерева в строку (любую: префиксную, инфиксную, обратную польскую).
• В различных расчётах на графах. Например, как часть алгоритма Диница поиска максимального потока.

Поиск в глубину — естественный выбор, когда агент (человек или робот) лично ходит по лабиринту и видит то, что непосредственно рядом с ним. «Правило левой руки» (идти, ведя левой рукой по стенке) будет поиском в глубину, если лабиринт древовидный (нет кружных путей).

• Поиск в ширину

• Левитин А. В. Глава 5. Метод уменьшения размера задачи: Поиск в глубину // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 212—215. — 576 с. — ISBN 978-5-8459-0987-9
• Кормен Т., Лейзерсон Ч., Ривест Р. Глава 22. Элементарные алгоритмы для работы с графами // Алгоритмы: построение и анализ(второе издание). — М.: «Вильямс», 2005. — С. 622—632.

• ВКИ НГУ: Методы программирования. Обходы графа.
• СпбГУ ИТМО, Факультет информационных технологий и программирования: Дискретная математика. Алгоритмы. Обход графа в глубину.
• Реализация поиска в глубину и различные задачи, решаемые с его помощью (сайт e-maxx.ru)
• Поиск в глубину
• Обход в глубину, цвета вершин — Викиконспекты ИТМО

Алгоритмы поиска на графах
Неинформированные методы	Алгоритм Брона — Кербоша Двунаправленный поиск Лучевой поиск Лексикографический поиск в ширину Поиск в ширину Поиск по критерию стоимости Поиск в глубину Поиск с возвратом Поиск восхождением к вершине Поиск с ограничением глубины Поиск в глубину с итеративным углублением
Информированные методы	Альфа-бета-отсечение Метод ветвей и границ Поиск по первому наилучшему совпадению A* B* D* Поиск точки перехода IDA* Рекурсивный поиск по первому наилучшему совпадению SMA*
Кратчайшие пути	Волновой алгоритм Алгоритм Беллмана — Форда Алгоритм Дейкстры Алгоритм Джонсона Алгоритм Левита Алгоритм Флойда — Уоршелла Поиск по краям
Минимальное остовное дерево	Алгоритм Борувки Алгоритм Прима Алгоритм Краскала
Другое	Алгоритм Британского музея Алгоритм Эдмондса Обход дерева Алгоритм ближайшего соседа в задаче коммивояжёра