Skip to content
Essay · Craft

When to use BFS vs DFS

When to use BFS vs DFS depends on what you need back: shortest steps, full exploration, or dependency order. Here is a decision rule, a worked grid example with real counts, and the memory trade-off that actually bites.

By Vishy9 min readPublished · 1 Nov 2026

When to use BFS vs DFS comes down to what the answer looks like. Use BFS when you need the shortest path in an unweighted graph or anything level by level. Use DFS when you need to explore every possibility, detect cycles, or order things by dependency. For plain reachability, either works, so pick by memory.

That rule fits on a sticky note, and it is right most of the time. The rest of this essay is about the cases where it is not obvious, and about why the rule holds, because an interviewer who asks "why BFS here?" is not satisfied by "because it is the shortest path one."

What is the real difference between BFS and DFS?

The only mechanical difference is the container that holds the frontier: BFS uses a queue and DFS uses a stack. Everything else, the shortest-path guarantee, the memory profile, the cycle detection, falls out of that one choice about which discovered node you process next.

Here is the framing I use. Imagine you lost a phone somewhere in a large office building. You can send a search party that sweeps floor by floor, every person checking the rooms at the same distance from the entrance before anyone goes farther. Or you can send one searcher with a ball of string who walks a corridor to its end, backs up only when stuck, and uses the string to know where the last fork was. The party is BFS: expensive in people (width), but whoever finds the phone first found it by the fewest doors. The string walker is DFS: cheap in people, since only one person is ever in the building, but the first route that works is whatever route happened to be tried first.

Notice what each one pays for. BFS pays in proportion to how wide the graph gets. DFS pays in proportion to how deep it gets. Most of the practical decisions are about which of those two numbers is small for your input.

When is BFS the right choice?

BFS is the right choice whenever the question is about the fewest steps, hops, moves, or levels in a graph where every edge costs the same. The reason is a simple invariant: a queue releases nodes in nondecreasing order of distance from the start, so the first time you pop a node, you have reached it by a shortest route.

You can prove that to yourself in two lines. Every node at distance d is enqueued by a node at distance d minus 1. Everything at distance d minus 1 is ahead of everything at distance d in the queue, because the queue is first in, first out. So distances come out sorted, and the first arrival at any node cannot be beaten. This is the same kind of argument that makes Dijkstra work, with the queue replaced by a priority queue, and it breaks the instant edges have different weights.

The typical BFS problems:

  • Minimum moves on a grid, a word ladder, a puzzle state space, a knight on a chessboard.
  • Level-order output for a tree: process one level, then the next.
  • Multi-source spread, such as the time for rot or fire to cover a grid. You enqueue every source at distance 0 and run one BFS. That is much cleaner than running a search from each source.
  • Nearest something: the closest exit, the closest 0 to every cell.

If the problem statement has the word "minimum" and the moves all cost the same, start by assuming BFS and look for a reason to leave. There is a longer treatment of this decision in the BFS vs DFS decision concept page.

When is DFS the right choice?

DFS is the right choice when you need to fully explore a branch before judging it: finding cycles, ordering by dependency, enumerating combinations, or computing something about a subtree from its children. The stack keeps you inside one branch, and the moment you back out of a node, you know everything beneath it has been finished.

That "finished" moment is what BFS cannot give you. In DFS each node has an entry time and an exit time, and the exit order is a post-order that is a reverse topological order on a directed acyclic graph. That is why topological sort has a natural DFS form, and why detecting a cycle in a directed graph is a matter of noticing an edge that points back to a node that is still on the current stack (a node that has been entered but not exited).

The typical DFS problems:

  • Cycle detection and ordering, as in Course Schedule.
  • Backtracking: permutations, subsets, N-Queens. The search tree is explored depth first because you build a partial answer, extend it, and undo the extension.
  • Subtree aggregates: height, diameter, maximum path sum. The answer for a node depends on its children, so you want children done first.
  • Connected components and flood fill, where order does not matter and a stack or recursion is the shortest code.

If you only need to know whether something is reachable, or to count regions, both traversals are correct. Then the decision is not about correctness at all. It is about memory and about how risky recursion is on your input.

How do the two compare on a real grid?

On a 1000 by 1000 open grid, BFS from one corner holds at most about 2,000 cells in its queue, while a DFS can hold close to 1,000,000 on its stack. Both do the same amount of work, roughly 4 million neighbour checks, but their memory and their answers differ enormously.

Work it through. The grid has 1,000,000 cells. Each cell has four neighbours, so a full traversal examines about 4,000,000 neighbour candidates, and each cell is marked visited once. That cost is identical for BFS and DFS: both are O(V + E), and on a grid E is about 2V.

Now ask for the shortest path from (0,0) to (500,500). The Manhattan distance is 1,000 moves, and BFS finds it. It expands cells in rings of equal distance. The ring at distance d has at most d + 1 cells until d reaches 999, and after that it shrinks, so the queue never holds more than about two rings at once, a couple of thousand entries. That is a few kilobytes of coordinates.

DFS on the same grid with a fixed neighbour order dives in one direction until it hits a wall or a visited cell, then turns. On an open grid it winds through the board like a snake, and the path it holds on its stack can be hundreds of thousands of cells long before it ever lands on (500,500). Two things go wrong. First, the path it returns is not the shortest one, and it has no reason to be. Second, if you wrote it recursively in Python, the default recursion limit of 1,000 frames stops it long before 1,000,000, so you get a RecursionError, not an answer. In Java or C++ you would hit a stack overflow at a depth somewhere in the tens of thousands, depending on frame size.

Here is the BFS version, which is the one I would write without hesitation for this question:

from collections import deque

def shortest_steps(n, start, goal, blocked):
    q = deque([(start[0], start[1], 0)])
    seen = {start}
    while q:
        r, c, d = q.popleft()
        if (r, c) == goal:
            return d
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n \
               and (nr, nc) not in seen and (nr, nc) not in blocked:
                seen.add((nr, nc))
                q.append((nr, nc, d + 1))
    return -1

One detail that matters: mark a cell as seen when you enqueue it, not when you pop it. If you wait until the pop, the same cell can sit in the queue several times, and on a grid each interior cell can be enqueued up to four times. That quadruples the queue and sometimes turns a fast solution into a time limit failure.

How does memory change with the shape of the graph?

BFS memory grows with the widest level, and DFS memory grows with the longest path, so the shape of the input decides which is cheaper. A balanced binary tree favours DFS, a long chain favours BFS, and a grid sits in between.

Take a perfectly balanced binary tree with 2^20 nodes, about a million. The bottom level has 2^19 nodes, 524,288, so BFS needs a queue of about half a million entries at its peak, while DFS needs a stack of depth 20. Now flip the shape: a linked-list-like tree of 1,000,000 nodes where each has one child. BFS holds one node at a time, and DFS holds a million frames. Same node count, opposite verdicts, a gap of five orders of magnitude in both directions.

PropertyBFSDFS
Frontier structureQueue (FIFO)Stack (LIFO) or recursion
TimeO(V + E)O(V + E)
Extra spaceO(widest level)O(longest path)
Fewest edges in unweighted graphGuaranteedNot guaranteed
Cycle detection, topological orderPossible (Kahn's algorithm) but indirectNatural, via entry and exit state
Backtracking and subtree resultsAwkwardNatural
Typical failureQueue blows up on wide graphs; duplicates if marked at popStack overflow on deep graphs; wrong answer if used for shortest path

The balanced tree example is also why people say "DFS uses less memory" as a rule. It is a statement about trees and about graphs with high branching, not a law. On a long thin graph the claim reverses.

Does the choice change the time complexity?

No. Both traversals are O(V + E) with an adjacency list, because each vertex is processed once and each edge is examined once or twice. What changes is how early you can stop and how big the constant factors are, not the asymptotic class.

With an adjacency matrix, both become O(V^2) since you scan a full row of V entries per vertex. On a 10,000 node sparse graph with 30,000 edges, that is the difference between about 40,000 steps and 100,000,000. This matters more than the BFS vs DFS choice does, and it is a common cause of surprising slowness. If you are reading a problem and the input is an edge list, build the adjacency list first.

Early exit is where the two differ in practice. If the target is close to the start, BFS finds it after touching only nearby nodes. If the target is deep and the graph is narrow, DFS can reach it without ever visiting the bulk of the graph. In the worst case, both touch everything. Do not claim one is faster without naming the input shape; I have watched candidates lose points for exactly that claim.

How do I decide between them in an interview?

Ask three questions in order. Do I need the fewest steps with equal edge costs? Then BFS. Do I need ordering, cycles, or results that depend on finished subtrees? Then DFS. If neither applies, is the graph deep or wide? Pick the traversal whose memory is small and say why out loud.

Some practical points that save you in the room:

  • Weighted edges end the BFS discussion. With weights, use Dijkstra, or a 0-1 BFS with a deque if every weight is 0 or 1.
  • Deep inputs call for an explicit stack. If the constraints allow 10^5 or 10^6 nodes in a chain, write DFS iteratively, or say that you would in production. In an interview, naming the recursion limit is often worth as much as the code.
  • Counting regions is a free choice. For Number of Islands, both work. Choose BFS if the grid might be one giant land mass, since the recursion depth can reach the cell count.
  • State the invariant. "The queue is ordered by distance, so the first pop of the goal is optimal" is a complete justification. Memorising which problems use which traversal is not.

The broader context for these choices sits in the graphs topic page, where traversal is the first of several tools that share this skeleton.

Frequently asked questions

Can DFS find the shortest path?

Not in general. DFS returns the first path it happens to find, which can be far longer than the best one. You can force it to be correct by exploring all paths and keeping the minimum, but that is exponential in the worst case, so for unweighted shortest paths BFS is the answer.

Does BFS work on weighted graphs?

Only if every edge has the same weight, or if weights are just 0 and 1, where a deque-based variant works. For arbitrary non-negative weights use Dijkstra, which is BFS with a priority queue. With negative weights you need Bellman-Ford.

Which is faster, BFS or DFS?

They have the same O(V + E) bound, so neither is faster in the worst case. The real differences are memory (widest level vs longest path) and how soon each reaches your target, which depends on where the target sits in the graph.

To make this concrete, open Number of Islands and solve it twice, once with a queue and once with an explicit stack, then compare the peak container size on a grid that is entirely land.