Explain BFS and DFS — when would you use each?
Breadth-First Search (BFS) and Depth-First Search (DFS) are the two fundamental graph traversal algorithms. Understanding when to use each requires knowing what each optimizes for.
BFS explores the graph level by level. It starts at a source node and visits all neighbors before moving to neighbors-of-neighbors. Internally it uses a queue (FIFO). Because it visits nodes in order of increasing distance from the source, BFS guarantees it finds the shortest path (in terms of edge count) in unweighted graphs. Time complexity is O(V + E) where V is vertices and E is edges. Space complexity is O(V) in the worst case, since you may hold an entire level of the graph in the queue simultaneously.
BFS is the right choice when: you need the shortest path in an unweighted graph or grid; you need to find all nodes within k hops of a source; you are doing level-order tree traversal; or you are solving problems where the optimal solution is the closest one.
DFS explores as far as possible along a path before backtracking. It uses a stack -- either an explicit one or the call stack via recursion. DFS does not guarantee a shortest path. Time complexity is also O(V + E). Space complexity is O(V) in the worst case for the recursion stack, but typically proportional to the depth of the deepest path.
DFS is the right choice when: you need to detect a path between two nodes (not necessarily shortest); you are detecting cycles; you need topological sort (DFS post-order on a DAG); you are exploring all solutions or permutations (backtracking); or you need to compute strongly connected components.
A key practical distinction: BFS can be infeasible on very deep or infinite graphs because the queue grows wide; DFS may hit recursion depth limits on very deep graphs. In interview problems, BFS is almost always the answer to minimum-steps questions; DFS is almost always the answer to does-a-path-exist or enumerate-all-solutions questions.
| Aspect | BFS | DFS |
|---|---|---|
| Data structure | Queue (FIFO) | Stack or recursion |
| Traversal order | Level by level | Branch to maximum depth first |
| Shortest path | Yes -- for unweighted graphs | No guarantee |
| Space complexity | O(V) -- wide frontier | O(depth) -- can be O(V) worst case |
| Cycle detection | Yes (track visited) | Yes (track visited or recursion state) |
| Topological sort | Kahn's algorithm (BFS-based) | DFS post-order |
| Best for | Shortest path, level-order, min-steps | Cycle detection, backtracking, topological sort |
Candidate correctly explains that BFS uses a queue and finds shortest paths while DFS uses a stack and goes deep first, but cannot articulate space complexity trade-offs, topological sort, or explain which to choose for specific problems.
Candidate explains both algorithms precisely, correctly distinguishes the shortest-path guarantee and why it holds for BFS, discusses space complexity trade-offs, names concrete use cases for each, and mentions DFS applications like cycle detection and topological sort.
Reading the answer is step one. Explaining it unprompted — under interview pressure — is what actually matters. Get AI-graded feedback on your answer with follow-up probes on your weak points.
Get Graded — Free Assessment