BFS, DFS & Graph Patterns
Graph problems are among the most feared in interviews, but most of them reduce to a small set of patterns. BFS for shortest paths and level-order traversal. DFS for exhaustive exploration and cycle detection. Topological sort for dependency ordering. Once you see a problem as a graph, the solution often writes itself.
The Core Insight
Most interview "graph" problems do not hand you an adjacency list. They hand you a grid, a list of prerequisites, a dictionary of words, or a tree structure. Your first job is to recognize the graph hiding inside the problem. Your second job is to pick BFS or DFS. Your third job is to code it cleanly.
BFS: Breadth-First Search
BFS explores nodes level by level. It uses a queue. It is the right tool when you need shortest path in an unweighted graph or when you need to process nodes by distance from a source.
The Template
function bfs(graph, start):
queue = [start]
visited = {start}
while queue is not empty:
node = queue.pop_front()
process(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.push_back(neighbor)
When to Use BFS
- Shortest path in unweighted graph
- Level-order traversal of a tree
- Minimum number of moves/steps/transformations
- "Nearest" or "closest" anything
- Spreading or flooding (rotting oranges, shortest bridge)
Example: Word Ladder
Given a start word, end word, and dictionary, find the shortest transformation sequence where each step changes exactly one letter.
start = "hit", end = "cog"
dict = ["hot", "dot", "dog", "lot", "log", "cog"]
BFS levels:
Level 0: hit
Level 1: hot
Level 2: dot, lot
Level 3: dog, log
Level 4: cog <-- found, answer is 5 (length of path)
Each word is a node. Two words are connected if they differ
by exactly one letter. BFS finds the shortest path.
The trick for efficiency: instead of comparing every pair of words (O(n^2 * L)), generate all possible one-letter changes for each word and check if they exist in the dictionary. With a hashset, each lookup is O(1).
BFS Level Tracking
Many problems need you to track which level you are on. Snapshot the queue length at the start of each level and process exactly that many nodes before incrementing the level counter. This is the standard approach for tree level-order traversal, minimum depth, right-side view, and similar problems.
DFS: Depth-First Search
DFS explores as deep as possible before backtracking. It uses a stack (or recursion, which is an implicit stack). It is the right tool when you need to explore all paths, detect cycles, or compute connected components.
The Template (Recursive)
function dfs(graph, node, visited):
visited.add(node)
process(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
The Template (Iterative)
function dfs(graph, start):
stack = [start]
visited = set()
while stack is not empty:
node = stack.pop()
if node in visited: continue
visited.add(node)
process(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.push(neighbor)
Use iterative DFS when recursion depth could blow the call stack (grids with 10,000+ cells, for instance). In interviews, mention this tradeoff even if you code the recursive version.
When to Use DFS
- Explore all paths (backtracking problems)
- Connected components
- Cycle detection
- Topological ordering
- Path existence (not shortest path)
- Tree traversals (preorder, inorder, postorder)
The Islands Problem
"Number of Islands" is the canonical grid-graph problem. A grid of '1' (land) and '0' (water), find how many connected components of land exist.
grid:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
Answer: 3 islands
The Approach
function numIslands(grid):
count = 0
for each cell (r, c) in grid:
if grid[r][c] == '1':
count += 1
dfs(grid, r, c) // sink the entire island
return count
function dfs(grid, r, c):
if r or c out of bounds: return
if grid[r][c] != '1': return
grid[r][c] = '0' // mark visited by sinking
dfs(grid, r-1, c) // up
dfs(grid, r+1, c) // down
dfs(grid, r, c-1) // left
dfs(grid, r, c+1) // right
You can also use BFS here. Both work. DFS is slightly cleaner for this problem because the recursive calls naturally handle the four-directional exploration.
Grid as Graph
This is the critical mental model. In a grid problem:
- Each cell is a node
- Each cell connects to its 4 (or 8) neighbors
- You do not need to build an adjacency list; the grid itself is the graph
Directional arrays for clean grid traversal:
dirs = [(-1,0), (1,0), (0,-1), (0,1)]
for (dr, dc) in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
// process neighbor
Cycle Detection
In Undirected Graphs
DFS with parent tracking. If you visit a neighbor that is already visited and is not the parent of the current node, there is a cycle.
function hasCycle(graph, node, parent, visited):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if hasCycle(graph, neighbor, node, visited):
return true
else if neighbor != parent:
return true // back edge = cycle
return false
In Directed Graphs
Use three states: unvisited, in-progress, completed. A back edge to an in-progress node means a cycle.
function hasCycleDirected(graph, node, state):
state[node] = IN_PROGRESS
for neighbor in graph[node]:
if state[neighbor] == IN_PROGRESS:
return true // cycle
if state[neighbor] == UNVISITED:
if hasCycleDirected(graph, neighbor, state):
return true
state[node] = COMPLETED
return false
This three-state approach is essential. Many candidates try to use simple visited/unvisited for directed graphs and get wrong answers.
Topological Sort
Given a directed acyclic graph (DAG), produce a linear ordering such that for every edge u -> v, u appears before v. This is the "course schedule" and "build order" pattern.
DFS-Based (Reverse Postorder)
function topoSort(graph):
visited = set()
result = []
for each node in graph:
if node not in visited:
dfsTopoSort(graph, node, visited, result)
return result.reversed()
function dfsTopoSort(graph, node, visited, result):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfsTopoSort(graph, neighbor, visited, result)
result.append(node) // postorder
BFS-Based (Kahn's Algorithm)
function topoSortBFS(graph):
inDegree = compute in-degree for each node
queue = all nodes with inDegree == 0
result = []
while queue is not empty:
node = queue.pop_front()
result.append(node)
for neighbor in graph[node]:
inDegree[neighbor] -= 1
if inDegree[neighbor] == 0:
queue.push_back(neighbor)
if result.length != number of nodes:
return "cycle detected, no valid ordering"
return result
Kahn's algorithm has an advantage: it naturally detects cycles (if the result does not contain all nodes, there is a cycle). It is also easier to reason about for many people. Use whichever you are more comfortable with.
Converting Problems Into Graph Problems
This is the real skill. Here are common transformations:
Problem domain -> Graph representation
Grid of cells -> Each cell is a node, neighbors are adjacent cells
Prerequisites/deps -> Directed edges from prereq to dependent
Word transformations -> Nodes are words, edges connect words differing by 1 char
State transitions -> Each state is a node, moves are edges
Social network -> People are nodes, relationships are edges
Example: Open the Lock
You have a 4-digit lock (0000 to 9999). Each move turns one wheel one step. Some combinations are "dead ends." Find the minimum moves from "0000" to the target.
This is BFS on a graph where:
- Each node is a 4-digit combination (10,000 nodes)
- Each node connects to 8 neighbors (4 wheels, each can go up or down)
- Dead ends are nodes you cannot visit
- You want shortest path from "0000" to target
Once you see it as a graph, it is straightforward BFS.
Choosing BFS vs DFS
Need shortest path/distance? -> BFS
Need to explore all possibilities? -> DFS (with backtracking)
Need level-by-level processing? -> BFS
Need topological ordering? -> Either (DFS is more common)
Need cycle detection? -> DFS (with state tracking)
Need connected components? -> Either
Grid flooding/spreading? -> BFS (for distance), DFS (for marking)
When in doubt and the problem does not require shortest path, DFS is usually simpler to code.
Common Pitfalls
- Forgetting the visited set. Without it, BFS and DFS loop forever on graphs with cycles. On grids, you can mark visited in-place (change the cell value), but mention the tradeoff of mutating input.
- Adding to visited too late. In BFS, mark a node as visited when you add it to the queue, not when you dequeue it. Otherwise, you add duplicates to the queue and waste time or get wrong answers.
- Using BFS for "all paths" problems. BFS finds shortest paths. If you need to enumerate or explore all paths, use DFS with backtracking.
- Wrong cycle detection for directed graphs. Simple visited/unvisited does not work for directed graphs. You need three states (unvisited, in-progress, completed).
- Not handling disconnected graphs. If the graph is not guaranteed to be connected, loop over all nodes and start BFS/DFS from each unvisited one.
- Stack overflow on large grids. Recursive DFS on a 1000x1000 grid means up to 1,000,000 recursive calls. Use iterative DFS or BFS instead.
Key Takeaways
- BFS and DFS are not hard algorithms. The hard part is recognizing that a problem is a graph problem and defining the nodes and edges.
- BFS is for shortest path and level-order. DFS is for exhaustive exploration and cycle detection. Do not mix them up.
- The islands problem pattern (grid traversal with DFS/BFS) appears in dozens of variations. Master it once and you handle all of them: max area, perimeter, number of distinct islands, shortest bridge.
- Topological sort is the answer whenever you see "ordering with dependencies." Course schedule, build order, task scheduling, compile order. Same pattern, different names.
- In the interview, draw the graph. Even if the problem is about words or locks or courses, sketch the nodes and edges. It makes the problem concrete and shows the interviewer you think in structures.