Top 25 Breadth First Search (BFS) Practice Problems

A Breadth First Search (BFS) is often used for traversing/searching a tree/graph data structure. The idea is to start at the root (in the case of a tree) or some arbitrary node (in the case of a graph) and explores all its neighbors, followed by the next-level neighbors, and so on.

Consider the following graph which marks the order in which the nodes would be discovered in BFS.

In this post, we have listed out some of the commonly asked interview questions that can be solved using the BFS algorithm:

1. Breadth-First Search (BFS)
2. Transitive closure of a graph
3. Check if a graph is strongly connected or not
4. Find root vertex of a graph
5. Chess Knight Problem | Find the shortest path from source to destination
6. Shortest path in a maze — Lee Algorithm
7. Find the shortest safe route in a field with sensors present
8. Flood Fill Algorithm
9. Count number of islands
10. Find the shortest path from source to destination in a matrix that satisfies given constraints
11. Find minimum passes required to convert all negative values in a matrix
12. Snake and Ladder Problem
13. Find the shortest distance of every cell from a landmine inside a maze
14. Check if an undirected graph contains a cycle or not
15. Find maximum cost path in a graph from a given source to a given destination
16. Total paths in a digraph from a given source to a destination having exactly `m` edges
17. Least cost path in a digraph from a given source to a destination having exactly `m` edges
18. Traverse a given directory using BFS and DFS in Java
19. Level order traversal of a binary tree
20. Depth-First Search (DFS) vs Breadth-First Search (BFS)
21. Bipartite Graph
22. Compute the least cost path in a weighted digraph using BFS
23. Find the path between given vertices in a directed graph
24. Print all nodes of a perfect binary tree in a specific order
25. Print right view of a binary tree
26. Find the minimum depth of a binary tree

Thanks for reading.