Graphs for Interviews: BFS vs DFS and When to Use Which

Graph questions scare people, but the hard part is rarely the graph. It is choosing the right traversal. Get BFS versus DFS right and most graph interview problems become bookkeeping. Get it wrong and you fight the algorithm the whole way.

Both visit every reachable node exactly once. Both run in O of V plus E time on an adjacency list. The difference is order, and order is everything for the question being asked.

The one rule that matters most

If the problem asks for a shortest path or minimum number of steps in an unweighted graph, use BFS. Full stop.

BFS explores in layers: all nodes one step away, then all nodes two steps away, and so on. The first time it reaches the target, it has reached it by the fewest edges possible. DFS gives you no such guarantee; it might dive down a long branch and find the goal via a needlessly long route.

For weighted graphs, neither plain traversal works, you want Dijkstra or its cousins, but for grids and unweighted edges, BFS is the answer.

When DFS is the better fit

DFS shines when the question is about structure rather than distance:

• Cycle detection. Track nodes on the current recursion stack; revisiting one means a cycle.
• Topological sort. A DFS post-order, reversed, gives a valid ordering for dependency graphs.
• Connected components and flood fill. Recursively mark everything reachable from a seed.
• Path existence and backtracking. When you need to explore, hit a dead end, and unwind.

DFS also tends to be shorter to write recursively, which matters when the clock is running.

Implementation gotchas that cost people offers

Most graph bugs are not exotic. They are these:

• Forgetting visited. Without a visited set you loop forever on cyclic graphs. Mark a node when you enqueue it for BFS, not when you dequeue it, or you will add duplicates.
• Mutating the wrong state in DFS. When backtracking, undo your changes on the way out or your path tracking corrupts.
• Stack overflow on deep graphs. Recursive DFS can blow the call stack on a long chain. Convert to an explicit stack if depth could reach into the tens of thousands.
• Mixing up the data structure. BFS needs a queue (FIFO). DFS needs a stack (LIFO) or recursion. Swap them and your traversal order silently breaks.

A quick decision checklist

Before you write a line, ask:

• Is it shortest path on unweighted edges? BFS.
• Is it level-by-level, like nodes per layer? BFS.
• Is it cycles, ordering, or component structure? DFS.
• Is it just "can I reach X"? Either, pick whichever you write faster.

That checklist resolves the vast majority of graph prompts in seconds.

Practice with intent

Graphs reward pattern recognition. The Algorithms track breaks traversals into focused lessons, and a structured roadmap sequences them so BFS and DFS reinforce each other instead of blurring together. When you want the full map of topics, start at Learn and pick your lane.

Once the choice between queue and stack feels automatic, you stop fearing the graph tag entirely. Want to pressure-test that instinct against problems tuned to your level? Step into the arena and find out if you can still beat the machine.