When to make use of DFS or BFS to unravel a Graph drawback?

Usually, after we come throughout a graph drawback, we’d have to traverse the construction of the given graph or tree to search out our resolution to the issue. Our drawback could be :

• To seek for a specific node within the graph.
• To search out the shortest distance from a node to every other node or to each different node.
• To rely all of the nodes.
• Or there may be extra complicated duties we have to carry out in the best way drawback defines us to do it.

However one factor is for positive we have to traverse the graph. Two very well-known strategies of traversing the graph/tree are Breadth-first-search (BFS) and Depth-first-search (DFS) algorithms.

The principle distinction between these two strategies is the best way of exploring nodes throughout our traversal-

• BFS:  Tries to discover all of the neighbors it could actually attain from the present node. It’ll use a queue information construction.
• DFS:  Tries to achieve the farthest node from the present node and are available again (backtrack) to the present node to discover its different neighbors. It will use a stack information construction.

Deciding what to make use of, BFS or DFS?

Many of the issues may be solved utilizing both BFS or DFS. It received’t make a lot distinction. For instance, take into account a quite simple instance the place we have to rely the whole variety of cities linked to one another. The place in a graph nodes characterize cities and edges characterize roads between cities.

In such an issue, we all know that we have to go to each node with the intention to rely the nodes. So it doesn’t matter if we use BFS or DFS as utilizing any of the methods we shall be traversing all the sides and nodes of a graph. So anyway time complexity shall be O(E+V) the place E is the whole variety of edges and V is the whole variety of nodes.

However there are issues when we have to resolve to both use DFS or BFS for a sooner resolution. And there’s no generalization. It fully is dependent upon the issue definition. It is dependent upon what we’re looking for within the resolution. We have to perceive clearly what our drawback desires us to search out. And the issue may not immediately inform us to make use of BFS or DFS. 

Let’s see a couple of examples for higher readability.

Examples of selecting DFS over BFS.

Instance 1:

Take into account an issue the place you’re standing at your own home and you’ve got a number of methods to go from your own home to a grocery retailer. You might be mentioned that each path you select has one retailer and is positioned on the finish of each path. You simply want to achieve any of the shops.

The apparent methodology right here shall be to decide on DFS. 

As we all know we will discover our resolution (grocery retailer) in any of the paths, we will simply go on traversing to any neighbor of the present node with out exploring all of the neighbors. There isn’t any want of going via BFS as it’ll unnecessarily discover different paths however we will discover our resolution by traversing any of the paths. Additionally, we all know that our resolution is located farthest from the start line so if we select BFS then we must virtually go to all of the nodes as we’re visiting all nodes of a stage and we are going to maintain doing it until the tip the place we discover a grocery retailer.

Instance 2:

Take into account an issue the place it’s essential print all of the nodes encountered in any one of many paths ranging from node A to node B within the diagram.

Right here there are two doable paths “A -> 4 -> 6 -> B” and “A -> 5 -> 6 -> B”.  Right here we require to maintain observe of a single path so there isn’t a want of exploring each different path utilizing BFS. Additionally, not each path will lead us from A to B. So we have to backtrack to the present node after which discover one other path and see if that leads us to B. Want for backtracking tells us that we will assume within the DFS course.

Examples of selecting BFS over DFS.

Instance 1:

Take into account an instance of a graph representing linked cities via edges. There are a couple of nodes coloured in crimson that signifies covid affected cities. White-colored nodes point out wholesome cities. You might be requested to search out out the time the covid virus will take to have an effect on all of the non-affected cities if it takes one unit of time to journey from one metropolis to a different.

Right here pondering of DFS isn’t even possible. Right here one affected metropolis will have an effect on all of its neighbors in a single unit of time. That is how we all know that we have to apply BFS as we have to discover all neighbors of the present node first. One other sturdy cause for BFS right here is that each nodes 0 and 11 will begin affecting neighbor cities concurrently. This reveals we require a parallel operation on each nodes 0 and 11. So we have to begin traversing all of the neighbor nodes of each nodes concurrently. So we will push nodes 0 and 11 within the queue and begin traversal parallelly. It’ll require 2 items of time for all of the cities to get affected.

1. At time = 0 items, Affected nodes = {0, 11}
2. At time = 1 items, Affected nodes = {0, 11, 3, 2, 8, 7, 6, 9}
3. At time = 2 items, Affected nodes = {0, 11, 3, 2, 8, 7, 6, 9, 5, 1, 4, 10}

Instance 2:

Take into account the identical instance of home and grocery shops talked about within the above part. Suppose now it’s essential discover the closest grocery retailer from the home as an alternative of any grocery retailer. Take into account that every edge is of 1 unit distance. Take into account the diagram beneath:

Right here utilizing DFS like earlier is not going to be possible. If we use DFS then we are going to journey down a path until we don’t discover a grocery retailer. However as soon as now we have discovered it we’re not positive if it’s the grocery retailer on the shortest distance. So we have to backtrack to discover a grocery retailer on different paths and see if every other grocery retailer has a distance lower than the present discovered grocery retailer. It will lead us to go to each node within the graph which isn’t most likely one of the simplest ways to do it.

We are able to use BFS right here as BFS traverses nodes stage by stage. We first test all of the nodes at a 1-unit distance from the home. If any of the nodes is a grocery retailer then we will cease else we are going to see the following stage i.e all of the nodes at a distance 2-unit from the home and so forth. It will take much less time in most conditions as we is not going to be traversing all of the nodes. For the given graph we are going to solely discover nodes as much as two ranges as on the second stage we are going to discover the grocery retailer and we are going to return the shortest distance to be 2.

Conclusion:

We are able to’t have fastened guidelines for utilizing BFS or DFS. It completely is dependent upon the issue we are attempting to unravel. However we will make some normal instinct.

• We are going to choose to make use of BFS after we know that our resolution would possibly lie nearer to the start line or if the graph has better depths.
• We are going to choose to make use of DFS after we know our resolution would possibly lie farthest from the start line or when the graph has a better width.
• If now we have a number of beginning factors and the issue requires us to start out traversing all these beginning factors parallelly then we will consider BFS as we will push all these beginning factors within the queue and begin exploring them first.
• It’s typically a good suggestion to make use of BFS if we have to discover the shortest distance from a node within the unweighted graph.
• We shall be utilizing DFS principally in path-finding algorithms to search out paths between nodes.

Though utilization of BFS or DFS isn’t solely restricted to those few issues. Yow will discover extra functions and utilization of BFS right here and DFS right here.