Graph BFS/DFS
Explore a graph by levels (BFS) or branches (DFS), tracking visited nodes.
Connected components, flood fill, shortest path in unweighted graph, islands, clone graph.
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 and 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.
Mark 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.
- Marking visited at dequeue in BFS, allowing the same node to be enqueued multiple times.
- Forgetting that recursive 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 DFS for shortest-path-in-unweighted-graph, getting a path that exists but isn't shortest.
- For multi-source BFS, initializing one source at a time and running BFS multiple times instead of seeding all sources before the first dequeue.
- Connected components: outer loop over nodes, BFS/DFS from each unvisited.
- Shortest path in unweighted graph: BFS with distance array.
- Flood fill / number of islands: grid BFS or DFS with 4-neighbor adjacency.
- Multi-source BFS: rotting oranges, walls and gates — seed all sources first.
- Bidirectional BFS: meet in the middle from source and target, ~sqrt the search space.
// 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
3Easiest first · Blind 75 above NeetCode 150