Depth first search (DFS) vs Breadth first search (BFS)

In this post, we will see the difference between Depth first search (DFS) and Breadth first search (BFS) algorithm which are used to traverse/search tree or graph data structure.

1. Definition

The Depth first search (DFS) algorithm starts at the root of the Tree (or some arbitrary node for a graph) and explores as far as possible along each branch before backtracking.
 
Breadth first search (BFS) algorithm also starts at the root of the Tree (or some arbitrary node of a graph), but unlike DFS it explores the neighbor nodes first, before moving to the next level neighbors. In other words, BFS explores vertices in the order of their distance from the source vertex, where distance is the minimum length of a path from source vertex to the node.

2. Examples

Below graph shows order in which the nodes are discovered in DFS.
DFS Tree
 
Below graph shows order in which the nodes are discovered in BFS.
Breadth first search (BFS) tree

3. Application

 
Below are the applications of DFS –
 
Below are the applications of BFS –
  • Copying garbage collection, Cheney’s algorithm
  • Finding the shortest path between two nodes u and v, with path length measured by number of edges (an advantage over depth first search)
  • Testing a graph for bipartiteness
  • Minimum Spanning Tree for unweighted graph
  • Web crawler
  • Finding nodes in any connected component of a graph
  • Ford–Fulkerson method for computing the maximum flow in a flow network
  • Serialization/Deserialization of a binary tree

4. DFS and BFS for Trees

Trees may be traversed in multiple ways in depth-first order or breadth-first order. Depth-first search for trees can be implemented using pre-orderin-order, and post-order while breadth-first search for trees can be implemented using level order traversal.
Beyond these basic traversals, various more complex or hybrid schemes are possible, such as depth-limited searches like iterative deepening depth-first search.

5. Implementation Details

In BFS, we need to maintain a separate data structure for tracking the tree/graph nodes yet to be visited. This is easily done iteratively using Queue data structure.
In contrast to BFS, DFS don’t need any additional data structure to store the tree/graph nodes. The recursive implementation of DFS uses the recursive call stack.

6. Time Complexity

 
The time complexity of both DFS and BFS traversal is O(N + M) where N is number of vertices and M is number of edges in the graph.
Please note that M may vary between O(1) and O(N2), depending on how dense the graph is.

7. Memory Requirements

The memory taken by DFS/BFS heavily depends on the structure of our tree/graph. The maximum memory taken by DFS (i.e. by recursion call stack) is equal to the depth of the tree and the maximum memory taken by BFS is equal to the width of the tree.

8. When to use DFS and BFS?

If we know the solution lies somewhere deep in a tree or far from the source vertex in graph, use DFS. If we know the solution is not that far from the source vertex, use BFS.
If our tree is very wide, use DFS as BFS will take too much memory. Similarly if our tree is very deep, choose BSF over DFS.


Learn More :