此示例中DFS与BFS之间的区别？ [英] Difference between DFS vs BFS in this example?

问题描述

在阅读

使用堆栈

  //使用堆栈
的迭代DFS public void dfsUsingStack（Node node）
 {
 Stack< Node> stack = new Stack< Node>（）; 
 stack.add（node）; 
 node.visited = true; 
 while（！stack.isEmpty（））
 {
节点元素= stack.pop（）; 
 System.out.print（element.data +）; 
 
 List< Node> neighbours = element.getNeighbours（）; 
 for（int i = 0; i 节点n = neighbours.get（i）; 
 if（n！= null&&！n.visited）
 {
 stack.add（n）; 
 n.visited = true; 
 
} 
} 
} 
} 
  

输出为
40,20,50,70,60,30,10

递归方法

  //递归DFS 
 public void dfs（节点节点）
 {
 System.out.print（ node.data +）; 
 List neighbours = node.getNeighbours（）; 
 node.visited = true; 
 for（int i = 0; i 节点n = neighbours.get（i）; 
 if（n！= null&！n.visited）
 {
 dfs（n）; 
} 
} 
} 
  

输出为
40,10,20,30,60,50,70与

通过查看代表探索节点的灰色点，您可以看到bfs的性质，类似于洪水。

I am bit confused after reading examples at DFS where output is printed in different fashion for both DFS approaches though both are said to be DFS.

In fact DFS recursion approach print the output just in same fashion as BFS. Then what's the difference ? Is recursion approach given here not an example of DFS ?

Using Stack

// 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;

                }
            }
        }
    }

Output is 40,20,50,70,60,30,10

Recursion Approach

// 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);
            }
        }
    }

output is 40,10,20,30,60,50,70 which is same as output under BFS

So what's the difference ?

解决方案

While the end result (a path) may be the same, the root difference between bfs and dfs (not the specific implementations posted) is in the search mechanism.
An obvious example is a case when only one path exists. In such case any good search algorithm (be it dfs, bfs or other) will eventually find that one path.
Where multiple path exist, bfs and dfs may find the same path or different paths. One of the charectaristics of bfs is that it finds the shortest path.
The core difference in the search mechanism is that bfs explores equally in all directions (hence the term breadth) , while dfs explores one (typically random) direction, all the way (hence the term depth) and "backtracks" if no solution found.
There are many resources which show visual representation of bfs and dfs such as this one.
Here is a screen capture of a tool I created to demonstrate and test traversal algorithms:

By looking at the grey dots which represent explored nodes, you can see the nature of the bfs, which analog to water flood.

这篇关于此示例中DFS与BFS之间的区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！