Поиск в глубину (DFS)

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

Поиск в глубину использует стек. Бывают рекурсивные реализации поиска в глубину и итеративные. Рекурсивные реализации поиска в глубину использую стек вызовов (call stack) для хранения своих промежуточных состояния. Недостатком такого подхода является ограничение на глубину стека что может приводить к stackoverflow (перполнению стека).

Итеративные реализации поиска в глубину используют структуру данных стек.

При поиске в глубину на каждой шаге существует коэфициент ветвления. Существуют разнообразные эвристики для ускорения поиска в глубину вроде метода ветвей и границ (оценки снизу и сверху), а также эвристика по наименее закрепленному состоянию (более подробнее читай книгу, например: Искусственный интеллект: современный подход Питера Норвига и Стюарта Рассела)