Поиск в глубину (DFS)
Идём вглубь до дна каждой ветки, а стек помнит, куда вернуться.
1function dfs(graph: Map<string, string[]>, start: string): string[] {2 const stack: string[] = [start]3 const visited = new Set<string>()4 const order: string[] = []5 6 while (stack.length > 0) {7 const node = stack.pop() as string8 if (visited.has(node)) continue9 10 visited.add(node)11 order.push(node)12 13 for (const next of graph.get(node) ?? []) {14 if (!visited.has(next)) stack.push(next)15 }16 }17 18 return order19}Проблема
Обойти все достижимые вершины графа, не заблудившись в циклах. BFS расширяет волну, DFS ныряет: сначала до упора по одной ветке, потом откатывается к последнему развилку.
Что вы видите
Граф и стек снизу. Вершина достаётся с верхушки стека, её соседи кладутся сверху — поэтому следующей обрабатывается «последняя найденная» вершина: путь уходит вглубь.
Как это работает
Стек (LIFO) — вся разница с BFS. Достаём вершину с верхушки, помечаем посещённой, непосещённых соседей кладём наверх. Рекурсивный DFS — тот же стек, только неявный в стеке вызовов. DFS находит компоненты связности, циклы, топологический порядок; кратчайший путь он не гарантирует.
Пошаговый разбор
- 01
Старт
Начальная вершина — в стек.
- 02
Достать с верхушки
Текущая вершина — верх стека; если посещена — пропустить.
- 03
Нырнуть
Непосещённых соседей — в стек: следующим будет последний положенный.
- 04
Откат
Ветка кончилась — стек сам возвращает к развилке.
- 05
Финал
Пустой стек — всё достижимое обойдено.
Complexity и ограничения
Память O(V). Порядок соседей влияет на маршрут обхода (но не на множество).
Edge cases
- Циклы
Пометка посещённости — единственная защита от вечного ныряния.
- Одна длинная ветка
Стек вырастает до длины пути — глубина рекурсии имеет предел.
- Дубликаты в стеке
Вершина может лечь в стек дважды — проверка посещённости при извлечении.
Где встречается в реальности
Обход файлов
Рекурсивный обход каталогов — DFS по дереву путей.
Поиск выхода из лабиринта
Метод «идём пока можно, откатываемся на развилках».
Топологическая сортировка
Порядок сборки зависимостей — DFS по графу зависимостей.
Связанные алгоритмы
«BFS идёт волной. А DFS — в глубину. Кто найдёт выход?»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.