BFS vs DFS — A Visual Guide to Graph Traversal

Breadth-first search and depth-first search are the two fundamental ways to explore a graph, and here is the secret that makes both trivial to remember: they are the same algorithm with one word changed. Keep the frontier of nodes-to-visit in a queue and you get BFS. Keep it in a stack and you get DFS. Everything else — visit orders, shortest-path guarantees, memory profiles, use cases — falls out of that single choice.

In this guide we will trace both algorithms on the *same* graph and watch them diverge, understand why BFS finds shortest paths and DFS does not, weigh the memory trade-offs, and build a practical decision rule for interviews and real code.

The one-word difference

Both algorithms keep a collection of discovered-but-not-yet-visited nodes, and both loop: take a node out, visit it, add its unvisited neighbours. The only question is *which* node comes out next. A queue is FIFO — first in, first out — so BFS visits nodes in the order they were discovered, finishing everything at distance 1 before touching anything at distance 2. A stack is LIFO — last in, first out — so DFS always chases the *most recently* discovered node, diving deeper and deeper before it ever backtracks.

traverse(graph, start):
  frontier = new Queue()   // BFS  — change this one line...
  frontier = new Stack()   // DFS  — ...and you get the other algorithm
  frontier.add(start); mark start discovered

  while frontier is not empty:
    u = frontier.remove()          // dequeue (BFS) or pop (DFS)
    visit(u)
    for each neighbour v of u:
      if v not discovered:
        mark v discovered
        frontier.add(v)

Same graph, two different journeys

Take a small undirected graph with six nodes and these edges (we will explore neighbours in alphabetical order in both traces):

• A — B
• A — C
• B — D
• C — E
• D — F
• E — F

Picture it as a ring: A at the top branching to B and C, B leading down to D, C leading down to E, and D and E meeting at F at the bottom.

BFS from A

1. Visit A. Enqueue B, C. Queue: [B, C]
2. Visit B (front of queue). Enqueue D. Queue: [C, D]
3. Visit C. Enqueue E. Queue: [D, E]
4. Visit D. Enqueue F. Queue: [E, F]
5. Visit E. F already discovered. Queue: [F]
6. Visit F. Done. Order: A, B, C, D, E, F

DFS from A (recursive)

1. Visit A, recurse into first neighbour B.
2. Visit B, recurse into D (A already visited).
3. Visit D, recurse into F.
4. Visit F, recurse into E (D already visited).
5. Visit E, recurse into C (F already visited).
6. Visit C — all neighbours visited. Unwind. Order: A, B, D, F, E, C

Same graph, same starting node, same neighbour ordering — completely different journeys. BFS went A, B, C, D, E, F: ring by ring, one full level at a time. DFS went A, B, D, F, E, C: it committed to the B-branch and rode it all the way to the bottom of the graph, reaching F third, then crawled back up the *other* side. C — a direct neighbour of A! — was visited *last*, because DFS only got to it by backtracking from the depths.

Why BFS guarantees shortest paths (in unweighted graphs)

BFS visits nodes in strictly non-decreasing order of distance from the source: every node at distance k is enqueued — and therefore dequeued — before any node at distance k+1 can even be discovered. So the *first* time BFS reaches a node, it arrived through the fewest possible edges. Record each node's parent at enqueue time and you can walk the pointers back to reconstruct an actual shortest path, not just its length. You can see the levels in the trace above: A (distance 0), then B and C (distance 1), then D and E (distance 2), then F (distance 3) — never out of order. The guarantee holds *only* while every edge counts the same; the moment edges carry weights, "fewest edges" stops meaning "cheapest", and you need Dijkstra's algorithm — which is exactly BFS with the queue upgraded to a priority queue. DFS makes no such promise: it happened to reach F along a 3-edge path here, but only because both routes to F tie at 3 edges. In general DFS finds *a* path, and on larger graphs often a wildly long one.

Memory: the trade-off nobody mentions until it hurts

Both algorithms are O(V + E) in time — every node and edge is touched a constant number of times. Memory is where they genuinely differ. BFS must hold an entire *frontier* level in the queue at once. On wide, bushy graphs that explodes: if each node has b neighbours, the frontier at depth d approaches b^d nodes. A social-network BFS two hops from a well-connected account can already be millions of entries. DFS instead holds one *path* from the root to the current node — O(depth). Its failure mode is the mirror image: on very deep graphs (long linked chains, big mazes, adversarial trees), recursive DFS can blow the call stack, since each level of depth is a stack frame.

When to use which

• Shortest path or "nearest X" in an unweighted graph → BFS. Fewest moves in a puzzle, closest exit in a maze, degrees of separation, minimum edits — anything phrased as "minimum number of steps".
• Cycle detection → DFS. A back edge to a node still on the current recursion path means a cycle; DFS exposes that path structure naturally.
• Topological sort → DFS. Finish-order of DFS on a DAG, reversed, is a valid topological order.
• Maze generation and backtracking puzzles → DFS. The dive-then-backtrack shape *is* the algorithm (recursive backtracker mazes, N-queens, Sudoku solvers).
• Connectivity and flood fill → either. Counting islands or connected components just needs *complete* exploration; pick whichever is more convenient (usually DFS for its three-line recursive form).
• Rule of thumb: if the answer involves the word "shortest" or "nearest", it is BFS; if it involves exploring structure, ordering, or exhausting possibilities, it is usually DFS.

Recursive vs iterative DFS

DFS has two standard implementations. The recursive version uses the *call stack* as its stack — elegant, three lines, and the natural fit for cycle detection and topological sort because pre/post-visit hooks fall out for free. The iterative version uses an explicit stack, exactly like the pseudocode above. Two things to know: first, the iterative version visits neighbours in *reverse* push order (last pushed pops first), so the two versions can produce different — but both valid — DFS orders unless you push neighbours reversed. Second, the iterative form is the safe choice on deep graphs: a million-node chain overflows most default call stacks, while an explicit stack just grows on the heap.

Where interviews use them

• BFS classics — shortest path in a binary matrix, word ladder, rotting oranges (multi-source BFS), binary tree level-order traversal, minimum knight moves.
• DFS classics — number of islands, course schedule (cycle detection + topological sort), clone graph, path sum in trees, generate parentheses and other backtracking.
• Either works — flood fill, connected components, checking if a path exists. Interviewers often accept both; being able to *say why you chose one* is the differentiator.

See the difference, not just read it

The queue-vs-stack distinction takes thirty seconds to memorize and one animation to actually understand. Run both traversals on the same graph, watch BFS ripple outward while DFS tunnels, and the visit orders will stop being trivia you memorize and start being shapes you can predict.