Multi tool use

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 ?

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 ?

40, 10, ...

30

40, 10, 30...

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

10-30

2 Answers
2

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.

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.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.