Поиск в глубину (DFS)
Обход графа, который уходит как можно глубже, прежде чем вернуться, — реализуется стеком (или рекурсией).
Три цвета для поиска циклов: белый (не посещена), серый (в обработке, лежит в стеке рекурсии), чёрный (завершена). Ребро в серую вершину означает цикл. Нужен для топологической сортировки, поиска компонент связности (Тарьян), генерации лабиринтов.
Временная сложность O(V+E). Память в худшем случае O(V) (глубокая рекурсия). Конкурент: BFS (очередь FIFO вместо стека, находит кратчайший путь в невзвешенном графе). Для глубоких графов рекомендуется итеративный DFS, чтобы не переполнить стек.