Breadth-first search (BFS) Practice Problems and Interview Questions

 

A Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors.

Below image shows order in which the nodes are expanded in BFS –

Breadth-first-tree

 

In this post, we have list out commonly asked interview questions that can be solved using BFS –

 

  1. Breadth First Search (BFS) | Iterative & Recursive Implementation
     
  2. Minimum number of throws required to win Snake and Ladder game
     
  3. Determine if given graph is Bipartite Graph or not
     
  4. Check if an undirected graph contains cycle or not
     
  5. Chess Knight Problem | Find Shortest path from source to destination
     
  6. Shortest path in a Maze | Lee algorithm
     
  7. Find shortest safe route in a field with sensors present
     
  8. Flood Fill Algorithm
     
  9. Count the number of islands
     
  10. Find Shortest path from source to destination in a matrix that satisfies given constraints
     
  11. Least Cost Path in Weighted Digraph using BFS
     
  12. Find maximum cost path in graph from given source to destination
     
  13. Least cost path in given digraph from given source to destination having exactly m edges
     
  14. Traverse the given directory using BFS and DFS in Java
     
  15. Find shortest distance of every cell from landmine in a Maze
     
  16. Check if given binary tree is complete binary tree or not
     
  17. Level Order Traversal of Binary Tree
     
  18. Total number of paths in given digraph from given source to destination having exactly m edges
     

 
 

Thank you for being with us. 🙂

 





Leave a Reply

avatar
  Subscribe  
Notify of