What is the difference between BFS (Breadth-First Search) and DFS (Depth-First Search) and their space-time complexities?
Quick Revision Summary
BFS uses a Queue and finds shortest unweighted paths. DFS uses a Stack/recursion and is ideal for topological sort and cycle detection.
Interactive Practice Mode
Formulate your thoughts or take notes before revealing the model solution.
Saved automatically
Model Answer & Deep-Dive Explanation
Breadth-First Search (BFS): Traverses graph level-by-level using a Queue (FIFO). It explores all direct neighbors at depth $d$ before moving to depth $d+1$.
- Use cases: Finding shortest path in unweighted graphs, finding closest peer nodes.
- Complexity: Time $O(V + E)$, Space $O(V)$ (stores maximum width of the graph).
Depth-First Search (DFS): Traverses graph branch-by-branch using a Stack (LIFO) or recursion. It explores as deep as possible along each branch before backtracking.
- Use cases: Topological sorting, cycle detection, maze solving, connected components.
- Complexity: Time $O(V + E)$, Space $O(h)$ where $h$ is maximum tree/graph recursion depth.
Interviewer Evaluation Points & Scoring Rubric
- 1 1. Distinguishes Queue vs Stack. 2. States O(V + E) time. 3. Connects BFS to shortest path and DFS to cycle detection.
Related Questions in Data Structures & Algorithms
How to detect a cycle in a Linked List using Floyd's Cycle-Finding Algorithm?
Intermediate level • 516 views
When would you choose a hash map instead of an array for lookups?
Easy level • 6 views
How do a stack and a queue differ, and where would each be useful?
Easy level • 6 views
How can you find two indices whose values sum to a target in one pass?
Medium level • 5 views
When does breadth-first search find a shortest path, and when is it the wrong choice?
Medium level • 5 views