Graph BFS/DFS

Junior

Explore a graph by levels (BFS) or branches (DFS), tracking visited nodes.

When to use

Connected components, flood fill, shortest path in unweighted graph, islands, clone graph.

Complexity

time O(n + m)space O(n)

BFS/DFS visits each vertex once and walks each adjacency edge once. The visited set, queue, or recursion stack can grow to O(n).

BFS layer-by-layer (A → B,C → D,E → F). DFS dives one branch deep first.

How it works

Breadth-first search (BFS) and depth-first search (DFS) are the two universal graph traversals. BFS uses a queue and visits in order of distance from the source — making it the right tool for shortest path in unweighted graphs, level-by-level exploration, and minimum-steps puzzles. DFS uses a stack (or recursion) and goes deep before wide — better for connectivity, cycle detection, topological sort, and any 'is there a path' question where shortest isn't required.

The visited set is non-negotiable for general graphs (trees don't need it because there are no back edges). For BFS, mark nodes visited when you enqueue them, not when you dequeue — otherwise the same node can be queued by multiple neighbors before being processed, blowing up the queue.

Grid problems (number of islands, flood fill, rotting oranges) are graph problems where edges are implicit (4- or 8-neighbor adjacency). The same BFS/DFS skeleton applies; the only addition is bounds checking on (r, c) before recursing. Multi-source BFS (rotting oranges) initializes the queue with all sources at once and propagates outward in lockstep — a powerful trick.

Key insight

Mark breadth-first search (BFS) nodes visited at enqueue, not dequeue — otherwise the same node can be queued by every neighbor before being processed, turning O(V + E) into O(V * E) in dense graphs.

Common pitfalls

Marking visited at dequeue in breadth-first search (BFS), allowing the same node to be enqueued multiple times.
Forgetting that recursive depth-first search (DFS) on a graph with millions of nodes can blow the stack — switch to iterative when depth is unbounded.
On grids, indexing (r, c) out of bounds before the visited check, NPE'ing or crashing.
Using depth-first search (DFS) for shortest-path-in-unweighted-graph, getting a path that exists but isn't shortest.
For multi-source breadth-first search (BFS), initializing one source at a time and running BFS multiple times instead of seeding all sources before the first dequeue.

Variations

Connected components: outer loop over nodes, breadth-first search (BFS) or depth-first search (DFS) from each unvisited.
Shortest path in unweighted graph: breadth-first search (BFS) with distance array.
Flood fill / number of islands: grid breadth-first search (BFS) or depth-first search (DFS) with 4-neighbor adjacency.
Multi-source breadth-first search (BFS): rotting oranges, walls and gates — seed all sources first.
Bidirectional breadth-first search (BFS): meet in the middle from source and target, ~sqrt the search space.

Template

// import java.util.*;
Set<Integer> visited = new HashSet<>();
Deque<Integer> stack = new ArrayDeque<>(); // or queue for BFS
stack.push(start);
visited.add(start);
while (!stack.isEmpty()) {
    int node = stack.pop();
    // process node
    for (int nb : graph.get(node)) {
        if (visited.add(nb)) {
            stack.push(nb);
        }
    }
}

Problems using this pattern

Easiest first · Blind 75 above NeetCode 150

Practice these problems

Solve mode — formulate the approach, then reveal. 3 problems.