Examples of choosing DFS over BFS.

Example 1:

Consider a problem where you are standing at your house and you have multiple ways to go from your house to a grocery store. You are said that every path you choose has one store and is located at the end of every path. You just need to reach any of the stores.

The obvious method here will be to choose DFS. 

As we know we can find our solution (grocery store) in any of the paths, we can just go on traversing to any neighbor of the current node without exploring all the neighbors. There is no need of going through BFS as it will unnecessarily explore other paths but we can find our solution by traversing any of the paths. Also, we know that our solution is situated farthest from the starting point so if we choose BFS then we will have to almost visit all the nodes as we are visiting all nodes of a level and we will keep doing it till the end where we find a grocery store.

Example 2:

Consider a problem where you need to print all the nodes encountered in any one of the paths starting from node A to node B in the diagram.

Here there are two possible paths “A -> 4 -> 6 -> B” and “A -> 5 -> 6 -> B”.  Here we require to keep track of a single path so there is no need of exploring every other path using BFS. Also, not every path will lead us from A to B. So we need to backtrack to the current node and then explore another path and see if that leads us to B. Need for backtracking tells us that we can think in the DFS direction.

Generally, when we come across a graph problem, we might need to traverse the structure of the given graph or tree to find our solution to the problem. Our problem might be :

• To search for a particular node in the graph.
• To find the shortest distance from a node to any other node or to every other node.
• To count all the nodes.
• Or there can be more complex tasks we need to perform in the way problem defines us to do it.

But one thing is for sure we need to traverse the graph. Two very famous methods of traversing the graph/tree are Breadth-first-search (BFS) and Depth-first-search (DFS) algorithms.

The main difference between these two methods is the way of exploring nodes during our traversal-

• BFS:  Tries to explore all the neighbors it can reach from the current node. It will use a queue data structure.
• DFS:  Tries to reach the farthest node from the current node and come back (backtrack) to the current node to explore its other neighbors. This will use a stack data structure.