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

Обходит граф, идя по одному пути как можно глубже, а затем возвращаясь к последней развилке. Стек на экране и есть этот путь.

O(V + E)
память O(V)
стек

Другие термины на этой странице

Вершина: точка графа, здесь нарисована кружком с буквой.
Ребро: линия, соединяющая две вершины. Здесь по нему можно пройти в обе стороны.
Соседи: вершины, соединённые с данной вершиной ребром. Их просматривают в алфавитном порядке.

0 / 60 шагов

в стеке
текущая
готова
ребро дерева поиска
пропущенное ребро

Скорость 8 шагов/с

Пробел: воспроизведение или пауза. Стрелки влево и вправо: шаг. Home и End: в начало или в конец.

Попробуйте: Выберите граф с циклами. Каждое пунктирное ребро ведёт назад к вершине, которая уже в стеке или готова: такое ребро замыкает цикл.

Как это работает

DFS вызывает сам себя для первого соседа, которого ещё не видел, затем для первого нового соседа этой вершины и так далее. Когда у вершины не остаётся новых соседей, её вызов заканчивается, а DFS возвращается на шаг назад и пробует там следующего соседа. Открытые вызовы образуют стек, который всегда совпадает с путём от старта до текущей вершины. Число рядом с вершиной показывает, какой по счёту её посетили.

Когда стоит применять

DFS помогает выяснить, куда вообще можно добраться, найти циклы, пройти лабиринт или упорядочить задачи, которые зависят друг от друга. Кратчайший путь он не находит.