Разница между DFS и BFS в этом примере?

Question

Я немного запутался после прочтения примеров на DFS , где выводится вывод по-разному для обоих подходов DFS, хотя оба, как говорят, являются DFS.

Фактически рекурсивный подход DFS печатает вывод точно так же, как BFS . Тогда какая разница? Приведенный здесь рекурсивный подход не является примером DFS?

Использование стека

// Iterative DFS using stack
    public  void dfsUsingStack(Node node)
    {
        Stack<Node> stack=new  Stack<Node>();
        stack.add(node);
        node.visited=true;
        while (!stack.isEmpty())
        {
            Node element=stack.pop();
            System.out.print(element.data + " ");

            List<Node> neighbours=element.getNeighbours();
            for (int i = 0; i < neighbours.size(); i++) {
                Node n=neighbours.get(i);
                if(n!=null && !n.visited)
                {
                    stack.add(n);
                    n.visited=true;

                }
            }
        }
    }

Вывод 40,20,50,70,60,30,10

Рекурсивный подход

// Recursive DFS
    public  void dfs(Node node)
    {
        System.out.print(node.data + " ");
        List neighbours=node.getNeighbours();
        node.visited=true;
        for (int i = 0; i < neighbours.size(); i++) {
            Node n=neighbours.get(i);
            if(n!=null && !n.visited)
            {
                dfs(n);
            }
        }
    }

вывод 40,10,20,30,60,50,70, что совпадает с выводом в BFS

Так в чем же разница?

Answer 1

Хотя конечный результат (путь) может быть одинаковым, основная разница между bfs и dfs (а не конкретными опубликованными реализациями) заключается в механизме поиска.
Очевидным примером является случай, когда существует только один путь. В таком случае любой хороший алгоритм поиска (будь то DFS, BFS или другой) в конечном итоге найдет этот путь.
Там, где существует несколько путей, BFS и DFS могут найти один и тот же путь или разные пути. Одна из характеристик bfs заключается в том, что она находит кратчайший путь.
Основное различие в механизме поиска состоит в том, что bfs исследует одинаково во всех направлениях (отсюда и термин «ширина»), в то время как dfs исследует одно (обычно случайное) направление, полностью (отсюда и термин «глубина») и «возврат», если решение не найдено.
Есть много ресурсов, которые показывают визуальное представление BFS и DFS, таких как это один.
Вот снимок экрана инструмента, который я создал для демонстрации и тестирования алгоритмов обхода:

Глядя на серые точки, которые представляют исследуемые узлы, вы можете увидеть природу бфс, аналога наводнения водой.

Answer 2

Первый подход совсем не DFS, по крайней мере, в каноническом определении алгоритма DFS. Это просто BFS, в которой кто-то заменил очередь на стек. Однако эта реализация достаточно хороша для «имитации» DFS в том смысле, что она обнаруживает вершины графа в DFS-подобном порядке. Его можно назвать «псевдо-DFS», если хотите, из-за порядка обнаружения, подобного DFS, но канонический алгоритм DFS намного больше этого.

Каноническая DFS не только следует за порядком обнаружения вершин в глубину, но также создает определенный порядок «обнаружения», определенный возвратный порядок (т. Е. Момент, когда «серая» вершина становится «черной») вершина в классической номенклатуре Дейкстры). В первой реализации эта важная особенность канонической DFS отсутствует (или ее невозможно реализовать каким-либо разумным способом).

Между тем, второй подход является явно рекурсивной реализацией классического алгоритма DFS.

В любом случае, в реальном DFS или псевдо-DFS не существует «одного истинного порядка», в котором следует посещать вершины. Обе реализации могут быть созданы для создания одного и того же порядка посещения вершин. В вашем случае никто просто не удосужился это сделать. Разница в выводе обусловлена ​​тем фактом, что прежняя реализация посещает соседей в обратном порядке - от последнего к первому. Все соседи сначала помещаются в стек, а затем выталкиваются один за другим в целях посещения. Поведение стека в LIFO - это то, что вызывает обращение. Между тем последняя реализация посещает соседей в порядке forward - от первого до последнего.

Если вы замените цикл в последней реализации на

for (int i = neighbours.size() - 1; i >= 0; --i) 

вы должны получить одинаковый порядок посещения (одинаковый вывод) в обеих реализациях.