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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the difference between DFS and BFS for graph problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”DFS explores as far as possible along each branch before backtracking. Uses a stack (explicit or call stack). Finds paths but not necessarily shortest paths. Best for: detecting cycles, topological sort, connected components, finding any path. BFS explores all neighbors at the current depth before going deeper. Uses a queue. Guarantees shortest path in unweighted graphs (minimum hop count). Best for: shortest path in unweighted graphs, level-order traversal, finding the nearest node with a property. Both are O(V+E). Choosing between them: if the problem asks "shortest path" or "minimum steps" in an unweighted graph, use BFS. If it asks "does a path exist" or "find all nodes reachable," either works – DFS is often simpler to code.”}},{“@type”:”Question”,”name”:”How does topological sort work and when do you need it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Topological sort orders the nodes of a DAG (Directed Acyclic Graph) such that for every edge u -> v, u comes before v. Kahn's algorithm: compute in-degree for all nodes, add all zero in-degree nodes to a queue, process each: decrement neighbor in-degrees, add newly-zero-in-degree neighbors to queue, count processed nodes. If count == total nodes: topological order found. If count < total nodes: cycle detected (some nodes never reached zero in-degree). Use topological sort when: scheduling tasks with dependencies (LC 207 Course Schedule), finding build order, processing events in dependency order. If a cycle exists (e.g., circular dependency), no topological sort exists.”}},{“@type”:”Question”,”name”:”How do you check if a graph is bipartite?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A bipartite graph can be 2-colored such that no two adjacent nodes share the same color. Algorithm: BFS/DFS, assign color 0 to the starting node, assign alternating colors to neighbors. If any neighbor already has the same color as the current node, the graph is not bipartite. Run from each unvisited node to handle disconnected graphs. O(V+E). Applications: scheduling where certain pairs cannot overlap (bipartite = valid coloring = schedule exists), detecting odd cycles (a graph is bipartite if and only if it contains no odd-length cycles). LC 785 (Is Graph Bipartite?), LC 886 (Possible Bipartition).”}},{“@type”:”Question”,”name”:”How do you solve the Course Schedule problem (LC 207, 210)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Model as a directed graph: course -> prerequisite edge. LC 207 (can finish all courses?): detect if a cycle exists. Use Kahn's: if processed count == n, no cycle, all courses can be finished. LC 210 (return valid order): return the topological order from Kahn's algorithm. Alternative: DFS 3-color. WHITE (unvisited), GRAY (in current DFS path), BLACK (fully processed). If we encounter a GRAY node during DFS, a cycle exists (back edge). When a node is fully explored, mark BLACK. Return the reversed post-order as the topological sort. Both approaches are O(V+E). Kahn's is typically easier to implement correctly and naturally detects cycles without a separate flag.”}},{“@type”:”Question”,”name”:”How do you solve the number of islands problem and its variants?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”LC 200 (count islands): DFS/BFS from each unvisited land cell, marking all reachable land as visited. Count the number of times we start a new traversal. Mark visited by changing '1' to '0' in-place (or use a visited set). O(rows * cols). LC 695 (max island area): track size during DFS, return maximum. LC 130 (surrounded regions): instead of counting islands, find 'O' cells connected to the border (DFS from border 'O' cells), mark them as temporary 'T', then flip all remaining 'O' to 'X' and restore 'T' to 'O'. LC 547 (number of provinces): graph is given as adjacency matrix – standard connected components DFS/Union-Find. All island variants follow the "connected components on a grid" template.”}}]}
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.