DFS vs BFS: When to Use Which, and How to Decide Fast

Depth-first and breadth-first search are the same twenty lines of code with one word changed. That is not a curiosity — it is the fastest way to remember both, and it is why choosing between them in an interview should take one sentence rather than a minute of hedging.

The problem it solves

You have a graph and you need to reach the nodes: all of them, or one specific one, or enough of them to answer a question. Both searches do exactly that, and both do it in O(V + E). So the choice is never about speed.

It is about order. Each search visits every reachable node, but the sequence differs, and several common questions are answerable only by one of the two sequences.

The intuition

Both algorithms run the identical loop: take a node from a container, mark it, put its unseen neighbours into the container. The container decides everything.

A stack returns the newest node, so the search plunges. A queue returns the oldest node, so the search spreads.

Depth-first commits. It takes one neighbour, then a neighbour of that, and keeps going until the branch dead-ends, only then reeling back to the last junction it owes a visit. Recursion is the natural way to write it because the call stack already is the container — which is also why an iterative version exists at all, for graphs deep enough to overflow it.

Breadth-first refuses to commit. It finishes everything one hop away before looking at anything two hops away, which gives it the property depth-first cannot have: the first time it reaches a node, it has reached it by the fewest possible edges.

Those two shapes imply four practical rules:

1. Shortest path in hops — BFS, always. First arrival equals minimum distance.
2. "Does a path exist" / "how many components" — either works, so pick the one that is easier to write. Recursive DFS is usually five lines shorter.
3. Anything about structure — cycles, topological order, bridges, backtracking — DFS. These are defined in terms of the descent and return, and only DFS has a moment of returning.
4. The answer is probably near the start — BFS, because it finds it before descending into a branch that might be enormous.

Watch it run

Follow the plunge: one branch to its end, then the walk back up to the most recent unexplored junction. Watch how far it travels before revisiting a node adjacent to the start.

Breadth-first over the same graph would have taken that adjacent node second. That difference is not cosmetic — it is the whole reason one of these finds shortest paths and the other does not.

The code

from collections import deque

graph = {
    "a": ["b", "c"],
    "b": ["a", "d"],
    "c": ["a", "d"],
    "d": ["b", "c", "e"],
    "e": ["d"],
}

def dfs(start):
    order, seen, stack = [], set(), [start]
    while stack:
        node = stack.pop()             # pop() -> newest first
        if node in seen:
            continue
        seen.add(node)
        order.append(node)
        for nb in reversed(graph[node]):
            if nb not in seen:
                stack.append(nb)
    return order

def bfs(start):
    order, seen, queue = [], {start}, deque([start])
    while queue:
        node = queue.popleft()         # popleft() -> oldest first
        order.append(node)
        for nb in graph[node]:
            if nb not in seen:
                seen.add(nb)
                queue.append(nb)
    return order

print(dfs("a"))    # ['a', 'b', 'd', 'c', 'e']
print(bfs("a"))    # ['a', 'b', 'c', 'd', 'e']

One word apart, two different orders. And the order is not a matter of taste — here is the distance each search believes it found, on a four-node cycle:

ring = {"a": ["b", "z"], "b": ["a", "c"], "c": ["b", "z"], "z": ["a", "c"]}

def dfs_depth(node, seen=None, d=0, out=None):
    if seen is None:
        seen, out = set(), {}
    seen.add(node); out[node] = d
    for nb in ring[node]:
        if nb not in seen:
            dfs_depth(nb, seen, d + 1, out)
    return out

def bfs_depth(start):
    dist, q = {start: 0}, deque([start])
    while q:
        n = q.popleft()
        for m in ring[n]:
            if m not in dist:
                dist[m] = dist[n] + 1
                q.append(m)
    return dist

print(dfs_depth("a"))   # {'a': 0, 'b': 1, 'c': 2, 'z': 3}
print(bfs_depth("a"))   # {'a': 0, 'b': 1, 'z': 1, 'c': 2}

z is a direct neighbour of a. DFS records it at depth 3, because it went the long way round the ring and marked z on arrival. The number is not a bug in the traversal — it is the honest depth at which DFS reached it, and it is why "DFS gives shortest paths" is false rather than approximately true.

The complexity

Both: O(V + E) time. Every node is handled once, every edge inspected once from each endpoint. Identical.

Space is where they diverge, and it depends on the graph's shape. BFS holds a whole frontier, so its peak is the widest level — on a broad, shallow graph that approaches V. DFS holds one root-to-leaf path, so its peak is the longest branch — on a deep, narrow graph that also approaches V, but on a wide shallow one it is tiny.

So: wide and shallow favours DFS on memory; deep and narrow favours BFS. Saying which shape you expect is a better answer than quoting O(V) for both.

Where it goes wrong

• Claiming DFS distances are shortest. The example above is the counterexample; keep one in your head.
• Recursive DFS on a deep graph. Python's default recursion limit is about a thousand frames. A path graph with 10,000 nodes raises RecursionError, and "I would convert it to an explicit stack" is the expected recovery.
• Dropping the seen check. On any graph with a cycle, both algorithms run forever. On a tree they are fine without it, which is exactly why the habit does not form until it costs you.
• Using BFS for weighted shortest paths. BFS counts edges. The moment edges have costs, fewest and cheapest are different questions and the answer is Dijkstra.
• Reversing neighbours by accident. An explicit stack visits neighbours in the reverse of the order you pushed them. The reversed() above exists only to make the iterative output match the recursive one; without it the traversal is still correct, just differently ordered, which matters when a test asserts an exact sequence.

How to say it in an interview

Pick with a reason, in one breath:

"Both are O(V + E), so I will choose on the property I need. This question asks for the fewest moves, and BFS reaches every node at its minimum hop count on first contact, so BFS — with a parent map if I have to output the route rather than its length. If it had asked whether a path exists, or about cycles or ordering, I would use DFS, because those are properties of the descent and DFS is the one that backtracks. The memory trade is frontier width versus path depth, and this graph is wide, so I will keep an eye on the queue."

Four sentences, and none of them is the pseudocode. That is the answer the question wanted.