top of page

Subscribe to Wisdom

Thanks for Subscribing!

  • Writer's picturePuru Uttam

BFS Vs DFS

BFS :

  • It stands for Breadth First Search.

  • It is a traversal algorithm which uses level order traversal which means all nodes of the same level are traversed first before moving on to the next level nodes.

  • It uses Queue for it's implementation(First In First Out/FIFO) instead of Stack to find the shortest path.

  • BFS covers all of it's neighbors while traversing.

  • It is widely preferred in programming over DFS as it is better than using recursion in some cases.

  • It is optimal as it covers shallowest nodes first and chances of missing the shortest path are less.

  • It’s precisely the space complexity that makes BFS impractical even though it’s complete and optimal in the cases where DFS isn’t.

  • It can require a lot of space and will prove to be inefficient if the branching factor is too large or the goal is deep.


Example:
        1             //levels 
       / \
      2   4
     /   / \
    3   5   6
    
    
Output : 1 2 4 3 5 6  as it follows Level Order Traversing


1 ->       1
     --------------             
          / \
2 ->     2   4
     ---------------
        /   / \
3 ->   3   5   6



DFS :

  • It stands for Depth First Search.

  • It is a traversal algorithm which uses stack data structure which works on the LIFO (Last In First Out) principle.

  • In DFS, all nodes are traversed in a depth-ward manner and then backtracking is performed to get back to the root.

  • It uses Stack for it's implementation instead of Queue to find the shortest path.

  • DFS is better when target is far from source

  • It reaches deep nodes faster than BFS.

  • It uses recursion to get to the end with base conditions.

  • DFS isn’t an optimal algorithm.

  • It's time complexity is high as compared to DFS.

  • DFS discovers a longer path first to reach to the goal.

  • BFS is impractical because of the high order of its space complexity. That is why DFS is used more often.


Example:
        1             //depth
       / \
      2   4
     /   / \
    3   5   6
    
    
Output : 1 2 3 4 5 6 

             .
1 ->        1.             
          /.  \ .
2 ->     2 .    4.
        / .   /.  \ .
3 ->   3 .   5.    6.
        .    .     .

You should know recursion, stack ,queue, priority queue, 0 and 1 based indexing before moving on to solve BFS and DFS questions.
11 views0 comments

Commenti


Modern Digital Watch
bottom of page