DFS vs. BFS: go deep or earn distance evenly.

The core difference is traversal order.

DFS follows one neighbor chain as far as it can, then backtracks. Recursion uses the call stack implicitly; an iterative version uses an explicit stack. BFS uses a queue to process nodes in first-in, first-out order, so all nodes at distance 1 are processed before distance 2.

Both can visit every reachable vertex. Their power comes from the order in which they expose the graph.

DFS vs. BFS at a glance

When should you use DFS?

DFS is a natural fit when the problem asks you to completely explore a connected region or recursively combine information from children.

dfs(node):
    if node is invalid or visited:
        return

    mark node visited
    process node

    for neighbor in neighbors(node):
        dfs(neighbor)

In a grid flood fill, the base cases reject out-of-bounds cells, walls or wrong colors, and already-seen cells. Mark the current cell before exploring its neighbors.

When should you use BFS?

BFS is the default test when every edge costs one step and the prompt asks for the minimum number of steps or the nearest reachable state. Layer order is the proof: the first time BFS reaches a node, no longer equal-cost path could have arrived earlier.

queue = [start]
mark start visited

while queue is not empty:
    node = remove front
    process node

    for neighbor in neighbors(node):
        if neighbor is not visited:
            mark neighbor visited
            add neighbor to back of queue

Mark on enqueue, not dequeue. Otherwise, multiple parents can add the same node before its first queue entry is processed.

What changes with weighted edges?

Plain BFS guarantees shortest paths only when every edge has equal cost. With nonnegative varying costs, Dijkstra’s algorithm uses a priority queue to process the closest unsettled state. With weights of only 0 or 1, a deque-based 0–1 BFS can be appropriate.

Why are both O(V + E)?

With an adjacency list and correct visited tracking, each vertex is marked once and each edge is inspected a constant number of times. That gives O(V + E) time. A graph may need O(V) visited storage, plus the DFS stack or BFS queue.

On an m × n grid, there are mn cells and each has at most four neighbor edges, so O(V + E) simplifies to O(mn). On a tree with n nodes and n − 1 edges, it simplifies to O(n).

Memory differs by shape. DFS on a long chain can have O(V) depth. BFS on a very wide level can hold O(V) frontier nodes. Neither is universally more memory-efficient.

Common traversal mistakes

• No visited state in a cyclic graph: the traversal can repeat forever.
• Marking too late: DFS should mark before exploring; BFS normally marks when enqueuing.
• Assuming DFS finds a shortest path: its first found route may be much longer.
• Using BFS with unequal weights: queue order no longer represents total path cost.
• Forgetting disconnected components: one start reaches only its connected region.
• Ignoring recursion depth: iterative DFS may be safer on deep inputs.

Continue learning

See the frontier

Practice DFS and BFS visually on iPhone.

Connect traversal order to the stack, queue, visited state, shortest-path proof, and complexity.