Explain BFS and DFS for graph traversal. When would you use one over the other?
Graph traversal is the building block for countless algorithms — shortest paths, cycle detection, topological sort, connected components, and more. Interviewers test whether you understand the mechanics and can choose the right traversal for a given problem.
Define BFS (uses a queue, explores level by level) and DFS (uses a stack or recursion, explores as deep as possible).
Give time and space complexity: both are O(V + E) time; BFS uses O(V) space for the queue, DFS uses O(V) for the recursion stack.
Explain when to use BFS: shortest path in unweighted graphs, level-order problems.
Explain when to use DFS: cycle detection, topological sort, path finding, solving puzzles like mazes.
BFS explores a graph level by level using a queue. Starting from a source node, it visits all neighbors before moving to the next level. This guarantees the shortest path in unweighted graphs, making it ideal for problems like finding the minimum number of moves or connections. DFS explores as deep as possible along each branch before backtracking, using recursion or an explicit stack. It is better for problems that need to explore all paths, detect cycles, or produce topological orderings. Both run in O(V + E) time where V is vertices and E is edges. BFS uses O(V) space for the queue in the worst case (widest level). DFS uses O(V) for the recursion stack in the worst case (longest path). I choose BFS for shortest path and level-order problems, and DFS for exhaustive search, cycle detection, and topological sort. For very deep graphs, iterative DFS avoids stack overflow. For very wide graphs, DFS uses less memory.
Always use a visited set to avoid infinite loops in graphs with cycles.
For shortest path in weighted graphs, use Dijkstra (BFS with priority queue), not plain BFS.
Know iterative DFS — interviewers sometimes ask you to convert recursive DFS to avoid stack overflow.
Yes, in unweighted graphs BFS guarantees the shortest path because it explores nodes level by level. For weighted graphs, use Dijkstra or Bellman-Ford.
A linear ordering of vertices in a DAG such that for every directed edge u→v, u comes before v. It can be computed using DFS (reverse post-order) or BFS (Kahn's algorithm).
In directed graphs, use DFS with three states (white/gray/black). A back edge to a gray node indicates a cycle. In undirected graphs, any edge to a visited node (not the parent) is a cycle.
HireMe AI listens to your interview in real-time, detects questions, and generates instant answer suggestions — so you never freeze up again.
Try HireMe AI Free