Question: Which of the following is true about breadth first search?
A BFS is nothing but Binary First Search
B BFS will get trapped exploring a single path
C The entire tree so far been generated must be stored in BFS
D BFS is not guaranteed to find a solution if exists
Answer: The entire tree so far been generated must be stored in BFS
| Aspect | Breadth-First Search (BFS) | Depth-First Search (DFS) |
| Basic Idea | Explores all neighbors of a node before moving to their children. | Explores as far as possible along each branch before backtracking. |
| Data Structure | Typically uses a queue to maintain a first-in, first-out (FIFO) order. | Typically uses a stack (or recursion) to maintain a last-in, first-out (LIFO) order. |
| Completeness | Guaranteed to find the shortest path in an unweighted graph. | May not find the shortest path; it depends on the order of traversal. |
| Memory Usage | Tends to use more memory due to the need to store all neighbors at each level. | Generally uses less memory because it only needs to store a single branch. |
| Time Complexity | O(V + E) (vertices + edges) for an adjacency list representation. | O(V + E) for an adjacency list representation, but may be faster in practice. |
| Space Complexity | O(V) for storage of visited nodes in an adjacency list representation. | O(V) for storage of visited nodes in an adjacency list representation. |
| Applications | Shortest path finding, connected components, web crawling. | Topological sorting, cycle detection, maze solving. |
| Algorithm Type | Greedy (tries all possibilities at the current level before moving deeper). | Recursive (dives as deep as possible before backtracking). |
| Path Representation | Finds the shortest path by exploring neighbors level by level. | May not find the shortest path; the first path discovered is not necessarily the shortest. |
| Implementation Complexity | Generally easier to implement using a queue. | May require recursion or a manually managed stack for implementation. |
| Use Case Example | Finding the shortest route on a map with equal road lengths. | Exploring a maze to find a possible exit. |