Поиск в глубину

---

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

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

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

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

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

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

---