Graph BFS/DFS Patterns — Complete Guide

BFS and DFS are both O(V+E) graph traversal algorithms, but they explore a graph in fundamentally different orders and are optimal for different problems. Choosing the wrong one does not give wrong answers on simple connectivity — but it gives wrong answers on shortest path, and it gives the right answer far more slowly when the wrong strategy is used.

BFS expands level by level, always visiting nodes in order of their distance from the source. This level-order property is what makes BFS the correct choice for shortest path in unweighted graphs, level-order traversal, and any problem asking for "nearest" or "minimum steps." DFS goes as deep as possible before backtracking, which makes it the right tool for all-paths enumeration, cycle detection, topological sort, and connectivity in disconnected graphs.

The practical decision rule: if the problem says "shortest," "minimum steps," or "nearest," reach for BFS. If the problem says "all paths," "detect cycle," "topological order," or just "connected components," reach for DFS.

The BFS template is queue-based and processes nodes level by level. Initialize a queue with the source node and a visited set. At each step, dequeue a node, process it, then enqueue all unvisited neighbors and immediately mark them visited. The first time you reach any node is the shortest path from the source.

Classic BFS problems include Rotting Oranges (minimum minutes for all oranges to rot), Walls and Gates (fill distances to nearest gate), Word Ladder (minimum transformations between words), and Shortest Path in Binary Matrix (minimum path from top-left to bottom-right). All of these ask for minimum steps, making BFS mandatory.

In Python: use collections.deque for O(1) popleft. In Java: use ArrayDeque. Never use a list as a queue — O(n) pop from front will TLE on large graphs. The visited set prevents revisiting nodes, and marking on enqueue (not dequeue) prevents duplicates in the queue.

Multi-source BFS starts from ALL source nodes simultaneously rather than a single source. You enqueue every source node at the beginning and run BFS normally. The result is that each cell gets the distance to its nearest source — not the distance from a single origin.

This technique is used in Walls and Gates (enqueue all gates, fill distance to nearest gate), Rotting Oranges (enqueue all rotten oranges, count minutes until all rot), and 01 Matrix (enqueue all zeros, fill distance to nearest zero). The key insight: running BFS from each source individually would be O(S * V) — multi-source BFS does all of them in a single O(V+E) pass.

Think of it as adding a virtual super-source connected to all real sources with zero-weight edges. Running BFS from the super-source is identical to multi-source BFS from all real sources simultaneously.

The DFS template uses recursion (or an explicit stack). Visit a node, mark it visited, then recursively visit all unvisited neighbors. DFS naturally handles all reachability from a source — if you reach a node, there is a path from the origin to it.

Classic DFS problems include Number of Islands (flood fill each island), Pacific Atlantic Water Flow (DFS from each ocean's boundary inward), Clone Graph (recursive clone), All Paths from Source to Target (backtracking DFS), and Course Schedule (cycle detection). DFS with a 3-state coloring (white=unvisited, gray=in-progress, black=done) is the standard technique for cycle detection in directed graphs.

DFS comes in three traversal orders: preorder (process node before children — useful for cloning trees), inorder (left, node, right — gives sorted order for BSTs), and postorder (process children before node — useful for topological sort, where a node is added to the result after all its dependencies are processed).

Bidirectional BFS searches from both the start and end nodes simultaneously, expanding the smaller frontier at each step. The search terminates when the two frontiers meet. This reduces the time complexity from O(b^d) to O(b^(d/2)), where b is the branching factor and d is the depth of the solution.

Word Ladder is the canonical bidirectional BFS problem. In a word graph where each word connects to all one-letter-away words, the branching factor can be very large. BFS from the start alone explores an exponentially growing frontier. Bidirectional BFS explores two much smaller frontiers and meets in the middle, often achieving 100x or more speedup in practice.

Implementation: maintain two visited sets (one per direction) and two queues. At each step, expand the smaller frontier. When you encounter a node already in the other frontier, you have found the shortest path — the total distance is the sum of the two frontier distances.

The most common BFS/DFS bugs fall into three categories: forgetting the visited set (causing infinite loops in cyclic graphs), incorrect visited marking timing (causing duplicates), and not handling disconnected components (missing entire parts of the graph).

For directed graphs, neighbor traversal only goes in the edge direction — if edge A→B exists, B is a neighbor of A but A is not a neighbor of B. Confusing directed and undirected traversal causes incorrect connectivity results. Always check whether the problem's graph is directed or undirected before building your adjacency list.

A subtle but critical BFS bug: marking nodes visited when you DEQUEUE them rather than when you ENQUEUE them. With dequeue-marking, the same node can be added to the queue multiple times before it is processed, causing O(V^2) space usage and wasted work. Always mark on enqueue.

Start with pure BFS problems to build the template: Rotting Oranges (multi-source BFS with time tracking), Word Ladder (graph BFS on word transformations), and Shortest Path in Binary Matrix (grid BFS with diagonal moves). These three cover 90% of BFS interview patterns.

For DFS, start with Number of Islands (basic flood fill), Pacific Atlantic Water Flow (reverse DFS from boundaries), and Clone Graph (recursive deep clone). Then move to Course Schedule for directed-graph cycle detection using 3-state DFS.

Mixed problems test your ability to choose: Evaluate Division is weighted DFS on a ratio graph. Alien Dictionary is topological sort (DFS postorder). Word Ladder II asks for all shortest paths — BFS for levels, DFS/backtracking for path reconstruction. The pattern recognition is the skill — once you identify the problem type, the algorithm follows.