Graph problems intimidate many candidates, yet nearly all of them reduce to two tools: breadth-first search (BFS) and depth-first search (DFS). If you can pick the right traversal, model the input as a graph and track visited nodes, you can solve a huge share of medium and hard questions at Google, Amazon, Microsoft and Meta. This guide gives you a decision framework, reusable templates and three worked problems.
Why Graph Traversal Dominates Interviews
Grids, dependency lists, word ladders, social networks and maps are all graphs in disguise. Interviewers use them to test whether you can recognize structure that the problem statement never names. Recognizing “this is a graph” is half the solution.
Signals That Point to a Graph
- A 2D grid where you move up, down, left and right.
- Items with prerequisites, dependencies or “can reach” relationships.
- Questions about connected components, shortest path or cycles.
- Transformations where one state moves to another by a small change (word ladder).
BFS vs DFS: How to Choose
Use BFS when you need the shortest path in an unweighted graph, or the minimum number of steps. BFS explores level by level using a queue, so the first time you reach a node is via the shortest route.
Use DFS when you need to explore all possibilities, count or label connected components, detect cycles, or perform a topological sort. DFS goes deep using recursion or an explicit stack and uses less memory on wide graphs.
The Two Templates
BFS Template
from collections import deque
def bfs(start, neighbors):
q = deque([start]); seen = {start}; steps = 0
while q:
for _ in range(len(q)):
node = q.popleft()
# process node
for nxt in neighbors(node):
if nxt not in seen:
seen.add(nxt); q.append(nxt)
steps += 1
DFS Template
def dfs(node, seen, neighbors):
seen.add(node)
for nxt in neighbors(node):
if nxt not in seen:
dfs(nxt, seen, neighbors)
Always mark nodes as visited when you enqueue them in BFS, not when you dequeue them. Otherwise the same node enters the queue many times and your runtime explodes.
Worked Example 1: Number of Islands (DFS on a Grid)
Given a grid of ‘1’ (land) and ‘0’ (water), count the islands. Scan every cell; when you find unvisited land, increment the count and flood-fill the whole island with DFS.
def num_islands(grid):
R, C = len(grid), len(grid[0]); count = 0
def dfs(r, c):
if r < 0 or c < 0 or r >= R or c >= C or grid[r][c] != '1':
return
grid[r][c] = '0'
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
dfs(r+dr, c+dc)
for r in range(R):
for c in range(C):
if grid[r][c] == '1':
count += 1; dfs(r, c)
return count
Time and space are O(R·C). Mention that you mutate the grid to mark visits, and offer a separate visited set if mutation is not allowed. For very large grids, note that recursion depth can overflow and switch to an iterative stack.
Worked Example 2: Rotting Oranges (Multi-Source BFS)
Every minute, rotten oranges infect fresh neighbors. Return the minutes until none are fresh. Push all rotten oranges into the queue at the start, then run BFS level by level; each level is one minute. This multi-source trick turns a seemingly simulation-heavy problem into a clean O(R·C) solution. Finish by checking whether any fresh orange remains, and return -1 if so.
Worked Example 3: Course Schedule (Cycle Detection)
Given prerequisites, can you finish all courses? This asks whether a directed graph has a cycle. Two reliable approaches exist:
- Kahn’s algorithm (BFS): compute in-degrees, repeatedly remove nodes with in-degree 0, and check that you removed every node.
- DFS with three states: unvisited, visiting, done. Reaching a “visiting” node means a cycle.
Both run in O(V+E). Interviewers often follow up with “return a valid order,” which is exactly the order Kahn’s algorithm produces.
Complexity Cheat Sheet
For adjacency lists, BFS and DFS cost O(V+E) time and O(V) space. On an R×C grid that becomes O(R·C). Say this unprompted; it signals maturity.
Common Mistakes to Avoid
- Forgetting the visited set and looping forever on cyclic graphs.
- Marking visited at dequeue time in BFS.
- Missing bounds checks on grids.
- Mixing up directed and undirected edges when building the adjacency list.
- Using DFS for shortest-path questions.
A 5-Day Graph Practice Plan
Day 1: Number of Islands and Max Area of Island. Day 2: Flood Fill and Rotting Oranges. Day 3: Clone Graph and Word Ladder. Day 4: Course Schedule I and II. Day 5: Pacific Atlantic Water Flow, then a timed mock where you explain your approach aloud.
Start Preparing Today
Choose one problem from the plan and solve it with the matching template before the day ends. Consistent, pattern-based practice beats cramming. For more interview preparation support, visit Niraswa AI and keep building one pattern at a time.
