Шаг | Стек (вершина →) | Берём | visited | result
----|--------------------|-------|-----------------|------------------
0 | [A] | A | {A} | [A]
1 | [C, B] | B | {A,B} | [A,B]
2 | [C, E, D] | D | {A,B,D} | [A,B,D]
3 | [C, E] | E | {A,B,D,E} | [A,B,D,E]
4 | [C, F] | F | {A,B,D,E,F} | [A,B,D,E,F]
5 | [C, E*, C] | C | {A,B,D,E,F,C} | [A,B,D,E,F,C]
(* E уже в visited — пропустим при извлечении)
Финальный результат: [A, B, D, E, F, C] ✓
Этот код, по сути, является готовой реализацией итеративного DFS, где стек берет на себя работу, которую в рекурсивной версии выполняет стек вызовов. Каждая часть здесь важна: множество
visited отслеживает уже обработанные узлы, список stack хранит узлы, которые предстоит обработать, а цикл while работает, пока есть что извлекать.Одна из классических задач, решаемых с помощью DFS, — поиск циклов в графе. Цикл — это ситуация, когда, двигаясь по графу, мы возвращаемся в узел, который уже встречали на текущем пути. Важно отличать просто посещенный узел от узла, находящегося в текущем стеке рекурсии. Ведь если мы видим уже посещенный узел, который не является частью текущего пути, это может быть просто пересечение, а не цикл. Поэтому в алгоритме используются два множества:
visited для всех узлов, которые когда-либо посещались, и rec_stack для узлов, в которых мы находимся прямо сейчас в процессе рекурсивного спуска.Граф БЕЗ цикла: Граф С циклом:
A A
/ \ / \
B C B C
| |\ /
D | X
|/ \
D E
Алгоритм запускает проверку из каждой вершины, чтобы учесть возможную несвязность графа. Если в процессе обхода мы наталкиваемся на соседа, который уже есть в
rec_stack, это означает обнаружение цикла.Пример 4
Как именно это работает, можно увидеть на примере графа с циклом. Начиная с A, мы идем в B, затем в D. В узле D видим соседа B, который уже есть в
rec_stack. Это и есть сигнал о наличии цикла.Пример 5
Еще одно важное практическое применение DFS — поиск пути в лабиринте. Здесь выбор между DFS и BFS зависит от конкретной задачи. Если нам нужно просто найти любой путь к выходу, DFS часто оказывается предпочтительнее. Он идет по одному пути до упора и, если лабиринт не слишком разветвлен, может найти выход довольно быстро. При этом DFS использует меньше памяти, так как хранит лишь текущий путь.
Пример 6
Однако если стоит задача найти кратчайший путь, DFS не подходит. Он может углубиться в длинную ветку и найти путь, который окажется далеко не самым коротким, в то время как существует более прямой маршрут. В такой ситуации BFS гарантированно найдет кратчайший путь, хотя и потребует больше памяти для хранения всех узлов текущего уровня.
Лабиринт: DFS может пойти так: BFS пойдёт так:
S S→A→C→E→EXIT S→A (длина 1)
/ \ (длина 4) S→B (длина 1)
A B Хотя существует S→A→C, S→B→EXIT
| | S→B→EXIT Найдёт S→B→EXIT
C EXIT (длина 2)! (длина 2) первым
\ /
E
|
EXIT
DFS нашёл путь длиной 4, хотя есть путь длиной 2.
BFS всегда находит кратчайший путь.
📟 Прилетело из @solidityset