Поиск в глубину (DFS)
Обходит граф, идя по одному пути как можно глубже, а затем возвращаясь к последней развилке. Стек на экране и есть этот путь.
- время O(V + E)
- память O(V)
- использует стек
Что это значит?
- Вершина: точка графа, здесь нарисована кружком с буквой.
- Ребро: линия, соединяющая две вершины. Здесь по нему можно пройти в обе стороны.
- Соседи: вершины, соединённые с данной вершиной ребром. Их просматривают в алфавитном порядке.
- Очередь: первым пришёл, первым ушёл. BFS всегда берёт вершину, которая ждёт дольше всех.
- Стек: последним пришёл, первым ушёл. DFS всегда продолжает с вершины, до которой добрался последней.
- V и E: число вершин и рёбер. O(V + E) значит, что каждая вершина и каждое ребро обрабатываются фиксированное число раз.
- в стеке
- текущая
- готова
- ребро дерева поиска
- пропущенное ребро
Начинаем с вершины A. Нажмите «Воспроизвести» или проходите поиск по шагам.
Пробел: воспроизведение или пауза. Стрелки влево и вправо: шаг. Home и End: в начало или в конец.
Попробуйте: Выберите граф с циклами. Каждое пунктирное ребро ведёт назад к вершине, которая уже в стеке или готова: такое ребро замыкает цикл.
Как это работает
DFS вызывает сам себя для первого соседа, которого ещё не видел, затем для первого нового соседа этой вершины и так далее. Когда у вершины не остаётся новых соседей, её вызов заканчивается, а DFS возвращается на шаг назад и пробует там следующего соседа. Открытые вызовы образуют стек, который всегда совпадает с путём от старта до текущей вершины. Число рядом с вершиной показывает, какой по счёту её посетили.
Когда стоит применять
DFS помогает выяснить, куда вообще можно добраться, найти циклы, пройти лабиринт или упорядочить задачи, которые зависят друг от друга. Кратчайший путь он не находит.