Graph Traversal Interview Patterns (2025)
Graph problems are among the most common in FAANG interviews — they appear as network problems, grid problems, tree variations, and dependency problems. Most reduce to one of a handful of traversal patterns. Master these and you can handle virtually any graph interview question.
Graph Representations
from collections import defaultdict, deque
from typing import Optional
# Adjacency list (most common in interviews)
graph: dict[int, list[int]] = defaultdict(list)
graph[1].extend([2, 3])
graph[2].extend([4])
graph[3].extend([4, 5])
# For weighted graphs
weighted: dict[int, list[tuple[int, int]]] = defaultdict(list)
# weighted[u].append((v, weight))
# Grid as implicit graph: neighbors are up/down/left/right
DIRS = [(0,1),(0,-1),(1,0),(-1,0)] # right, left, down, up
def neighbors(r, c, rows, cols):
return [(r+dr, c+dc) for dr, dc in DIRS if 0 <= r+dr < rows and 0 <= c+dc < cols]
Pattern 1: BFS — Shortest Path in Unweighted Graph
# Standard BFS: shortest path from source to all nodes
def bfs(graph: dict, source: int) -> dict[int, int]:
dist = {source: 0}
queue = deque([source])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in dist:
dist[neighbor] = dist[node] + 1
queue.append(neighbor)
return dist
# Word Ladder (LeetCode 127): shortest transformation sequence
from collections import defaultdict
def ladder_length(beginWord: str, endWord: str, wordList: list[str]) -> int:
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)]) # (word, steps)
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word == endWord:
return steps + 1
if next_word in word_set and next_word not in visited:
visited.add(next_word)
queue.append((next_word, steps + 1))
return 0
# BFS on Grid: Rotting Oranges (LeetCode 994)
def oranges_rotting(grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0)) # (row, col, minutes)
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while queue:
r, c, t = queue.popleft()
minutes = max(minutes, t)
for nr, nc in neighbors(r, c, rows, cols):
if grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc, t + 1))
return minutes if fresh == 0 else -1
Pattern 2: DFS — Connected Components and Flood Fill
# Number of Islands (LeetCode 200): count connected components
def num_islands(grid: list[list[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r = rows or c = cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited in-place
dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count
# DFS iterative (avoids recursion limit for large grids)
def num_islands_iterative(grid: list[list[str]]) -> int:
rows, cols = len(grid), len(grid[0])
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
stack = [(r, c)]
grid[r][c] = '0'
while stack:
cr, cc = stack.pop()
for nr, nc in neighbors(cr, cc, rows, cols):
if grid[nr][nc] == '1':
grid[nr][nc] = '0'
stack.append((nr, nc))
return count
# Pacific Atlantic Water Flow (LeetCode 417): multi-source DFS
def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
rows, cols = len(heights), len(heights[0])
pacific, atlantic = set(), set()
def dfs(r, c, visited, prev_height):
if (r, c) in visited or r = rows or c = cols:
return
if heights[r][c] < prev_height:
return
visited.add((r, c))
for dr, dc in DIRS:
dfs(r+dr, c+dc, visited, heights[r][c])
# Run DFS from ocean borders backwards (water flows uphill in reverse)
for r in range(rows):
dfs(r, 0, pacific, heights[r][0])
dfs(r, cols-1, atlantic, heights[r][cols-1])
for c in range(cols):
dfs(0, c, pacific, heights[0][c])
dfs(rows-1, c, atlantic, heights[rows-1][c])
return [[r, c] for r in range(rows) for c in range(cols)
if (r, c) in pacific and (r, c) in atlantic]
Pattern 3: Cycle Detection
# Directed graph: DFS with three colors
# White (0) = unvisited, Gray (1) = in current path, Black (2) = done
def has_cycle_directed(graph: dict[int, list[int]], n: int) -> bool:
color = [0] * n
def dfs(node):
color[node] = 1 # gray: currently exploring
for neighbor in graph[node]:
if color[neighbor] == 1:
return True # back edge → cycle
if color[neighbor] == 0 and dfs(neighbor):
return True
color[node] = 2 # black: done
return False
return any(dfs(i) for i in range(n) if color[i] == 0)
# Course Schedule (LeetCode 207): can you finish all courses?
def can_finish(numCourses: int, prerequisites: list[list[int]]) -> bool:
graph = defaultdict(list)
for course, prereq in prerequisites:
graph[prereq].append(course)
# 0=unvisited, 1=visiting(cycle check), 2=done
state = [0] * numCourses
def dfs(node):
if state[node] == 1: return False # cycle
if state[node] == 2: return True # already verified
state[node] = 1
if not all(dfs(nb) for nb in graph[node]):
return False
state[node] = 2
return True
return all(dfs(i) for i in range(numCourses))
# Undirected graph: Union-Find for cycle detection
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y) -> bool:
px, py = self.find(x), self.find(y)
if px == py:
return False # already connected → adding this edge creates a cycle
if self.rank[px] bool:
uf = UnionFind(n)
for u, v in edges:
if not uf.union(u, v):
return True
return False
Pattern 4: Bipartite Check
# Is Graph Bipartite? (LeetCode 785): 2-colorable using BFS
def is_bipartite(graph: list[list[int]]) -> bool:
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] # opposite color
queue.append(neighbor)
elif color[neighbor] == color[node]:
return False # same color on both sides of edge
return True
Pattern 5: Topological Sort (Kahn’s Algorithm)
# Course Schedule II (LeetCode 210): return topological order
def find_order(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
graph = defaultdict(list)
in_deg = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_deg[course] += 1
queue = deque(i for i in range(numCourses) if in_deg[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_deg[neighbor] -= 1
if in_deg[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == numCourses else [] # [] = cycle detected
Pattern 6: Minimum Spanning Tree (Prim’s / Kruskal’s)
import heapq
# Prim's Algorithm: grow MST by always adding the cheapest edge from the current tree
def min_cost_connect_all(n: int, edges: list[list[int]]) -> int:
"""LeetCode 1584: Min Cost to Connect All Points"""
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((w, v))
graph[v].append((w, u))
visited = set([0])
heap = [(w, v) for w, v in graph[0]]
heapq.heapify(heap)
total_cost = 0
while heap and len(visited) int:
edges.sort(key=lambda e: e[2]) # sort by weight
uf = UnionFind(n)
total = 0
for u, v, w in edges:
if uf.union(u, v):
total += w
return total
Pattern Cheat Sheet
| Problem Type | Pattern | Key Problems |
|---|---|---|
| Shortest path (unweighted) | BFS | Word Ladder (127), Rotting Oranges (994), 01 Matrix (542) |
| Connected components / flood fill | DFS or BFS | Number of Islands (200), Pacific Atlantic (417) |
| Cycle detection (directed) | DFS 3-color | Course Schedule (207), Detect Cycle in Directed Graph |
| Cycle detection (undirected) | Union-Find | Redundant Connection (684), Graph Valid Tree (261) |
| Dependency ordering | Topological Sort | Course Schedule II (210), Alien Dictionary (269) |
| 2-colorable partition | BFS coloring | Is Graph Bipartite? (785), Possible Bipartition (886) |
| Minimum spanning tree | Prim’s or Kruskal’s | Min Cost Connect All Points (1584), Connecting Cities (1135) |
Interview Tips
- Grid problems are graphs: A cell is a node; edges connect adjacent cells. BFS gives shortest path; DFS gives connected components
- State matters: When the same node can be visited in different states (Word Ladder, keys+rooms), add state to the visited set:
(node, state) - Prefer iterative DFS for large inputs: Python’s default recursion limit is 1000. Use an explicit stack to avoid RecursionError
- BFS vs DFS for grids: BFS for “shortest path to X,” DFS for “can we reach X” or “count all reachable cells”
- Union-Find vs DFS for connected components: Union-Find handles dynamic connectivity (edges added over time); DFS is simpler for static graphs
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”When should you use BFS vs DFS for graph problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”BFS: use when you need the shortest path in an unweighted graph (each edge has cost 1). BFS explores level by level — the first time you reach a node is via the shortest path. Use it for: Word Ladder, Rotting Oranges, 0-1 Matrix, minimum steps problems. DFS: use when you need to explore all possibilities, find connected components, or don’t need the shortest path. DFS goes deep before backtracking — natural for: Number of Islands (flood fill), cycle detection, topological sort, permutations/combinations. For grid problems: BFS for “minimum distance to X,” DFS for “count all cells satisfying Y.” When in doubt about path optimality: BFS. When in doubt about exhaustive exploration: DFS.”}},{“@type”:”Question”,”name”:”How do you detect a cycle in a directed vs undirected graph?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Directed graph: DFS with 3-color marking. White (unvisited) → Gray (currently in recursion stack) → Black (fully processed). A back edge (from Gray to Gray) indicates a cycle. Gray-to-Gray means we found a node that is an ancestor of the current node in the DFS tree — forming a cycle. Used in Course Schedule (207). Undirected graph: DFS with parent tracking (don’t go back to the node we came from — that’s not a cycle). Or use Union-Find: process edges one by one; if both endpoints are already in the same component (find(u) == find(v)), adding this edge creates a cycle. Union-Find is preferred for undirected because it also handles dynamic edge addition.”}},{“@type”:”Question”,”name”:”What is topological sort and how do you implement it with Kahn’s algorithm?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Topological sort orders nodes in a DAG such that for every directed edge (u, v), u appears before v. It’s impossible if the graph has a cycle. Kahn’s Algorithm (BFS-based): compute in-degree for all nodes. Add all nodes with in-degree 0 to a queue (no dependencies). Process queue: pop a node, add to result, decrease in-degree of all its neighbors; add any neighbor with in-degree now 0. If the result has all nodes, return it — otherwise a cycle exists (some nodes could never reach in-degree 0). Applications: course scheduling (Course Schedule II), build order, package dependency resolution. O(V+E) time.”}}]}
🏢 Asked at: Meta Interview Guide 2026: Facebook, Instagram, WhatsApp Engineering
🏢 Asked at: Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture
🏢 Asked at: Coinbase Interview Guide
🏢 Asked at: Uber Interview Guide 2026: Dispatch Systems, Geospatial Algorithms, and Marketplace Engineering
🏢 Asked at: LinkedIn Interview Guide 2026: Social Graph Engineering, Feed Ranking, and Professional Network Scale
🏢 Asked at: Atlassian Interview Guide
🏢 Asked at: Apple Interview Guide 2026: iOS Systems, Hardware-Software Integration, and iCloud Architecture