CODEWITHSUNDEEP
algorithmgraph-theorydepth-first-searchbreadth-first-search
user3198603
user3198603

Reputation: 5836

Difference between DFS vs BFS in this example?

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 ?

enter image description here

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 ?

Upvotes: 1

Views: 4421

Answers (2)

c0der
c0der

Reputation: 18812

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:

enter image description here

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

enter image description here

Upvotes: 5

AnT stands with Russia
AnT stands with Russia

Reputation: 320787

The first approach is not DFS at all, at least in the canonical definition of DFS algorithm. It is simply BFS in which someone replaced a queue with a stack. However, this implementation is good enough to "mimic" DFS in a sense that it discovers graph vertexes in DFS-like order. It can be called "pseudo-DFS", if you wish, because of DFS-like discovery order, but canonical DFS algorithm is much more than that.

The canonical DFS not only follows depth-first vertex discovery order, but also produces certain "undiscovery" order, certain backtracking order (i.e. the moment when "gray" vertex becomes "black" vertex in classic Dijkstra's nomenclature). In the first implementation this important feature of canonical DFS is not present (or it is impossible to implement in any reasonable way).

Meanwhile, the second approach is an explicitly recursive implementation of the classic DFS algorithm.

In any case, real DFS or pseudo-DFS, there's no "one true order" in which the vertices should be visited. Both implementations can be made to produce the same vertex visitation order. In your case nobody simply bothered to ensure that. The difference in output is caused by simple fact that the former implementation visits neighbors in reverse order - from last to first. All neighbors are first pushed into a stack and then popped one-by-one for visitation purposes. The LIFO behavior of the stack is what produces the reversal. Meanwhile, the latter implementation visits neighbors in their forward order - from first to last.

If you replace the cycle in the latter implementation with

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

you should end up with identical visitation order (identical output) in both implementations.

Upvotes: 2

Related Questions