Graph Traversal Interview Patterns
Graph problems appear in nearly every senior engineering interview. The key is recognizing which traversal fits the problem and executing it cleanly. This guide covers the core templates you need.
DFS Template for Graphs
Use a visited set (not a visited array) when nodes are not integer indices. Recursive DFS is concise; iterative DFS with an explicit stack avoids recursion depth limits on large graphs.
# Recursive DFS
def dfs(graph, node, visited):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Iterative DFS (explicit stack)
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return visited
The iterative version is safer for interview problems with large inputs where Python’s recursion limit (default 1000) could trigger a RecursionError. Use sys.setrecursionlimit as a fallback if you prefer recursive.
BFS Template
BFS with a deque gives level-by-level traversal. It finds the shortest path in unweighted graphs because it explores all nodes at distance k before any node at distance k+1.
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
distance = {start: 0}
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
return distance
# Level-by-level BFS (useful when you need to process one level at a time)
def bfs_levels(graph, start):
visited = set([start])
current_level = [start]
while current_level:
next_level = []
for node in current_level:
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
next_level.append(neighbor)
current_level = next_level
Connected Components
Count connected components by running DFS or BFS from each unvisited node. Every time you start a new traversal, you’ve found a new component. Relevant problems: LC 200 (Number of Islands), LC 547 (Number of Provinces), LC 695 (Max Area of Island).
def count_components(n, edges):
graph = {i: [] for i in range(n)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
components = 0
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
for node in range(n):
if node not in visited:
dfs(node)
components += 1
return components
For grid problems (LC 200), treat each cell as a node and its 4 neighbors as edges. DFS from each unvisited land cell and mark cells visited by setting grid[r][c] = ‘0’ to avoid a separate visited set.
Topological Sort – Kahn’s BFS Algorithm
Kahn’s algorithm processes nodes in topological order using an in-degree array. Start with all zero-in-degree nodes. After processing a node, decrement the in-degree of its neighbors and enqueue any that reach zero. If the number of processed nodes equals the total node count, the graph is a DAG. Otherwise a cycle exists. Relevant problems: LC 207 (Course Schedule), LC 210 (Course Schedule II).
from collections import deque
def topo_sort_kahn(n, prerequisites):
graph = [[] for _ in range(n)]
in_degree = [0] * n
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(order) == n:
return order # valid topological order
return [] # cycle detected
# LC 207: can finish all courses?
def can_finish(num_courses, prerequisites):
return len(topo_sort_kahn(num_courses, prerequisites)) == num_courses
Topological Sort – DFS with 3-Color Marking
Three states: WHITE (unvisited), GRAY (in current DFS path), BLACK (fully processed). If you reach a GRAY node during DFS, you’ve found a back edge – a cycle exists. This is equivalent to detecting a node that’s still on the current recursion stack.
WHITE, GRAY, BLACK = 0, 1, 2
def topo_sort_dfs(n, prerequisites):
graph = [[] for _ in range(n)]
for course, prereq in prerequisites:
graph[prereq].append(course)
color = [WHITE] * n
order = []
has_cycle = [False]
def dfs(node):
if has_cycle[0]:
return
color[node] = GRAY
for neighbor in graph[node]:
if color[neighbor] == GRAY:
has_cycle[0] = True
return
if color[neighbor] == WHITE:
dfs(neighbor)
color[node] = BLACK
order.append(node) # post-order = reverse topological order
for i in range(n):
if color[i] == WHITE:
dfs(i)
if has_cycle[0]:
return []
return order[::-1]
Bipartite Check (2-Coloring)
A graph is bipartite if you can color it with 2 colors such that no two adjacent nodes share a color. BFS from each unvisited node, alternating colors. If you encounter a neighbor with the same color as the current node, the graph is not bipartite. Relevant problems: LC 785 (Is Graph Bipartite?), LC 886 (Possible Bipartition).
from collections import deque
def is_bipartite(graph):
n = len(graph)
color = [-1] * n # -1 = uncolored
for start in range(n):
if color[start] != -1:
continue
queue = deque([start])
color[start] = 0
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if color[neighbor] == -1:
color[neighbor] = 1 - color[node]
queue.append(neighbor)
elif color[neighbor] == color[node]:
return False # same color = not bipartite
return True
Key insight: odd-length cycles make a graph non-bipartite. Trees are always bipartite.
Flood Fill and Island Problems
Grid DFS is a special case of graph DFS where the graph is implicit. Move in 4 (or 8) directions. Mark visited cells by modifying the grid in-place (if mutation is allowed) or by using a visited set. Relevant problems: LC 130 (Surrounded Regions), LC 200 (Number of Islands), LC 695 (Max Area of Island).
def max_area_of_island(grid):
rows, cols = len(grid), len(grid[0])
def dfs(r, c):
if r = rows or c = cols or grid[r][c] == 0:
return 0
grid[r][c] = 0 # mark visited
area = 1
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
area += dfs(r + dr, c + dc)
return area
return max(dfs(r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 1)
# LC 130: mark border-connected 'O' cells as safe, then flip remaining 'O' to 'X'
def solve(board):
rows, cols = len(board), len(board[0])
def dfs(r, c):
if r = rows or c = cols or board[r][c] != 'O':
return
board[r][c] = 'S' # safe
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(r + dr, c + dc)
for r in range(rows):
for c in range(cols):
if (r in (0, rows-1) or c in (0, cols-1)) and board[r][c] == 'O':
dfs(r, c)
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O':
board[r][c] = 'X'
elif board[r][c] == 'S':
board[r][c] = 'O'
Tarjan’s Algorithm for Strongly Connected Components
Tarjan’s SCC algorithm is an interview awareness topic – you won’t be asked to implement it from scratch in most interviews, but you should know what it does and when to apply it.
A strongly connected component (SCC) is a maximal set of nodes where every node is reachable from every other node (in a directed graph).
Tarjan’s algorithm works in a single DFS pass using two key values per node:
- disc[v] – discovery time (DFS order)
- low[v] – lowest discovery time reachable from the subtree rooted at v
When low[v] == disc[v], node v is the root of an SCC. Pop the stack up to and including v to get the SCC members.
Time complexity: O(V + E). Use cases: finding cycles in directed graphs, condensation DAG, 2-SAT problems.
Decision Guide: DFS vs BFS
| Problem Type | Algorithm | Why |
|---|---|---|
| Connected components | Either DFS or BFS | Both work; DFS is slightly simpler to code |
| Shortest path (unweighted) | BFS | BFS guarantees shortest path by level order |
| Topological sort | Kahn’s BFS or DFS post-order | Kahn’s detects cycles naturally; DFS is more intuitive |
| Detect cycle (directed) | 3-color DFS | GRAY node = back edge = cycle |
| Detect cycle (undirected) | DFS with parent tracking | Revisiting a non-parent node = cycle |
| Bipartite check | BFS 2-coloring | BFS makes color alternation natural |
| Flood fill / islands | DFS (recursive) | Simpler recursive code for grid traversal |
| Strongly connected components | Tarjan’s or Kosaraju’s DFS | SCC requires DFS-based post-order processing |
Rule of thumb: if the problem asks for shortest path or level-order processing, reach for BFS. If it asks for path existence, component membership, or ordering, DFS is usually simpler.
Meta coding interviews heavily test graph traversal. See common patterns for Meta interview: graph traversal and BFS/DFS problems.
LinkedIn interviews test social graph algorithms and traversal. See patterns for LinkedIn interview: graph algorithms and social network traversal.
Uber interviews cover graph algorithms for routing and dispatch. See patterns for Uber interview: graph traversal and road network algorithms.