Ответ 1
Ваше замешательство связано с тем, что вы, по-видимому, предполагаете, что алгоритм DFS можно получить из алгоритма BFS, заменив очередь FIFO на стек LIFO.
Это популярное заблуждение - это просто неправда. Классический алгоритм DFS не может быть получен путем замены очереди BFS на стек. Разница между этими алгоритмами гораздо важнее.
Если вы возьмете алгоритм BFS и просто замените очередь FIFO на стек LIFO, вы получите то, что можно назвать псевдо-DFS-алгоритмом. Этот алгоритм псевдо-DFS действительно правильно воспроизведет последовательность прямого прохождения вершин DFS, но он не будет иметь эффективность пространства DFS и не будет поддерживать обратный трафик DFS (обратный трассировка).
Между тем, истинная классическая DFS не может быть получена из BFS такой наивной заменой очереди на стек. Классический DFS - это совершенно другой алгоритм со значительно отличающейся структурой ядра. True DFS - это подлинно рекурсивный алгоритм, который использует стек для целей обратного отслеживания, а не для хранения открытия вершины "спереди" (как в случае с BFS). Наиболее непосредственным следствием этого является то, что в алгоритме DFS максимальная глубина стека равна максимальному расстоянию от вершины начала в обходе DFS. В алгоритме BFS (как и в вышеупомянутом псевдо-DFS) максимальный размер очереди равен ширине самого большого фронта открытия вершины.
Самый яркий и экстремальный пример, иллюстрирующий разницу в потреблении пиковой памяти между DFS и BFS (а также псевдо-DFS), - это звездный график: одна центральная вершина, окруженная большим числом (например, 1000) периферийных вершин, причем каждая периферийная вершина связана с центральной вершиной ребром. Если вы запустите BFS на этом графике, используя центральную вершину в качестве источника, размер очереди сразу же перейдет к 1000. То же самое произойдет, если вы используете псевдо-DFS (т.е. Если вы просто замените очередь на стек). Но для классического алгоритма DFS потребуется глубина стека только 1 (!), Чтобы пройти весь этот граф. Увидеть разницу? 1000 по сравнению с 1. Это то, что имеется в виду благодаря лучшей эффективности использования пространства DFS.
В принципе, возьмите любую книгу об алгоритмах, найдите описание классической DFS и посмотрите, как она работает. Вы заметите, что разница между BFS и DFS намного шире, чем простая очередь и стек.
P.S. Следует также сказать, что можно построить пример графика, который будет иметь меньшее потребление пиковой памяти в BFS. Таким образом, утверждение о лучшей эффективности использования пространства DFS должно рассматриваться как нечто, что может применяться "в среднем" к некоторому подразумеваемому классу "хороших" графиков.