Graph problems appear in every serious technical interview. They cover a wide range of difficulty — from simple BFS/DFS traversal to Dijkstra and Union-Find. The good news: most graph interview problems reduce to one of six patterns. Recognizing the pattern is half the solution.
Graph Representation
Two standard representations:
# Adjacency list (most common for sparse graphs)
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # undirected
# Adjacency matrix (dense graphs or when O(1) edge lookup needed)
n = 5
adj = [[0]*n for _ in range(n)]
for u, v in edges:
adj[u][v] = adj[v][u] = 1Pattern 1: Connected Components (DFS / BFS)
Count connected components or check if all nodes are reachable. Classic: Number of Islands, Number of Provinces.
def numComponents(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v); graph[v].append(u)
visited = set()
count = 0
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
for i in range(n):
if i not in visited:
dfs(i)
count += 1
return countFor grids: treat each cell as a node, neighbors are the 4 (or 8) adjacent cells. Mark visited by modifying the grid in-place to avoid an extra set.
Pattern 2: Shortest Path in Unweighted Graph (BFS)
BFS guarantees the shortest path in unweighted graphs — the first time a node is reached is via the shortest path. Use for: minimum number of steps, minimum word transformations (Word Ladder), minimum moves on a grid.
from collections import deque
def bfs_shortest_path(graph, start, end):
queue = deque([(start, 0)]) # (node, distance)
visited = {start}
while queue:
node, dist = queue.popleft()
if node == end:
return dist
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return -1 # no pathMulti-source BFS: add all sources to the queue initially. The distance to each cell is from the nearest source. Used for: 01 Matrix (distance to nearest 0), Rotting Oranges (distance from any rotten orange).
Pattern 3: Shortest Path in Weighted Graph (Dijkstra)
Dijkstra finds shortest paths from a source when edge weights are non-negative. Time O((V + E) log V) with a min-heap.
import heapq
def dijkstra(graph, start):
# graph[u] = [(weight, v), ...]
dist = {node: float("inf") for node in graph}
dist[start] = 0
heap = [(0, start)] # (distance, node)
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry, skip
for weight, v in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(heap, (dist[v], v))
return distLeetCode applications: Network Delay Time (743), Cheapest Flights Within K Stops (787, modified Dijkstra), Path With Minimum Effort (1631).
Pattern 4: Topological Sort (Kahn or DFS)
Order nodes such that all edges point forward. Use for: task scheduling, course prerequisites, build dependency resolution.
from collections import deque
def topological_sort(n, prerequisites):
in_degree = [0] * n
graph = defaultdict(list)
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 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)
return order if len(order) == n else [] # empty list = cyclePattern 5: Union-Find (Disjoint Set Union)
Dynamically group elements and query if two elements are in the same group. O(alpha(n)) ≈ O(1) amortized with path compression and union by rank.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.components = 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):
px, py = self.find(x), self.find(y)
if px == py:
return False # already connected
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.components -= 1
return TrueUse for: detecting cycles in undirected graphs, minimum spanning tree (Kruskal), redundant connection, accounts merge.
Pattern 6: Cycle Detection
Undirected: Union-Find or DFS (track parent to avoid revisiting). Directed: DFS with three-color marking (white=unvisited, gray=in-stack, black=done). If you encounter a gray node, there is a cycle.
def hasCycle(n, edges):
# Directed graph
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
def dfs(u):
color[u] = GRAY
for v in graph[u]:
if color[v] == GRAY:
return True # back edge = cycle
if color[v] == WHITE and dfs(v):
return True
color[u] = BLACK
return False
return any(dfs(i) for i in range(n) if color[i] == WHITE)Grid as Graph
Many graph problems disguise themselves as grid problems. Treat each cell (r, c) as node r*cols+c. Neighbors are the 4 adjacent cells. Apply BFS/DFS/Union-Find as normal. Common patterns: flood fill (Number of Islands), BFS for minimum distance (01 Matrix, Walls and Gates), DFS for reachability (Pacific Atlantic Water Flow, Surrounded Regions).
Recognition Guide
| Pattern | Signal in Problem |
|---|---|
| BFS (unweighted shortest) | “minimum steps,” “minimum transformations,” level-order |
| Dijkstra | “minimum cost/distance,” weighted graph, non-negative weights |
| Bellman-Ford | “negative weights,” “detect negative cycle,” “at most K edges” |
| Topological sort | “dependency order,” “course prerequisites,” DAG |
| Union-Find | “connected components,” “number of groups,” “merge accounts” |
| DFS backtrack | “find all paths,” “paths with constraint” |
Frequently Asked Questions
When should you use Dijkstra vs BFS vs Bellman-Ford?
BFS finds shortest paths in unweighted graphs (or where all edge weights are equal) in O(V + E) time. It is the first choice for: minimum hops, minimum steps on a grid, Word Ladder. Dijkstra handles weighted graphs with non-negative weights in O((V + E) log V) with a min-heap. Use for: network routing, minimum cost path when weights represent distances or costs. Bellman-Ford handles negative weights and detects negative cycles in O(V * E) time — much slower than Dijkstra. Use when: the graph may have negative edges (currency arbitrage, relaxed shortest path with K stops). In LeetCode, Bellman-Ford appears in problems with a constraint on number of edges (Cheapest Flights Within K Stops) where Dijkstra without modification would not respect the K-hop limit.
How does Union-Find detect cycles in an undirected graph?
Union-Find detects cycles by tracking connected components. Initialize each node as its own component. Process edges one by one: for each edge (u, v), find the root of u and the root of v. If they share the same root, u and v are already in the same component, meaning this edge creates a cycle — return True. If different roots, union them (merge the two components) and continue. After processing all edges without finding a shared root, return False — no cycle. This approach runs in O(E * alpha(V)) ≈ O(E) time. Compare with DFS cycle detection: DFS also runs O(V + E) but requires explicit recursion and a visited/in-stack state. Union-Find is simpler for undirected graphs. For directed graphs, Union-Find does not apply because directionality matters — use three-color DFS (white/gray/black) instead.
What is topological sort and which problems require it?
Topological sort orders the nodes of a DAG (Directed Acyclic Graph) such that for every directed edge from u to v, u appears before v in the ordering. It is only possible in acyclic graphs — if a cycle exists, no valid ordering exists and Kahn's algorithm returns fewer nodes than expected. Two implementations: (1) Kahn's BFS algorithm: initialize a queue with all nodes of in-degree 0; repeatedly dequeue a node, add to result, and decrement neighbors' in-degrees; add any neighbor that reaches 0 to the queue. (2) DFS: after finishing all neighbors of a node, push it to a stack; the stack is the topological order in reverse. Problems requiring topological sort: Course Schedule I and II (LeetCode 207, 210), Alien Dictionary (reconstruct character order from sorted words), Task Scheduling (tasks with prerequisites), Build Systems (Maven, Make — build targets before their dependents). Recognition signal: "do X before Y" constraints on a set of tasks or nodes.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When should you use Dijkstra vs BFS vs Bellman-Ford?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “BFS finds shortest paths in unweighted graphs (or where all edge weights are equal) in O(V + E) time. It is the first choice for: minimum hops, minimum steps on a grid, Word Ladder. Dijkstra handles weighted graphs with non-negative weights in O((V + E) log V) with a min-heap. Use for: network routing, minimum cost path when weights represent distances or costs. Bellman-Ford handles negative weights and detects negative cycles in O(V * E) time — much slower than Dijkstra. Use when: the graph may have negative edges (currency arbitrage, relaxed shortest path with K stops). In LeetCode, Bellman-Ford appears in problems with a constraint on number of edges (Cheapest Flights Within K Stops) where Dijkstra without modification would not respect the K-hop limit.”
}
},
{
“@type”: “Question”,
“name”: “How does Union-Find detect cycles in an undirected graph?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Union-Find detects cycles by tracking connected components. Initialize each node as its own component. Process edges one by one: for each edge (u, v), find the root of u and the root of v. If they share the same root, u and v are already in the same component, meaning this edge creates a cycle — return True. If different roots, union them (merge the two components) and continue. After processing all edges without finding a shared root, return False — no cycle. This approach runs in O(E * alpha(V)) ≈ O(E) time. Compare with DFS cycle detection: DFS also runs O(V + E) but requires explicit recursion and a visited/in-stack state. Union-Find is simpler for undirected graphs. For directed graphs, Union-Find does not apply because directionality matters — use three-color DFS (white/gray/black) instead.”
}
},
{
“@type”: “Question”,
“name”: “What is topological sort and which problems require it?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Topological sort orders the nodes of a DAG (Directed Acyclic Graph) such that for every directed edge from u to v, u appears before v in the ordering. It is only possible in acyclic graphs — if a cycle exists, no valid ordering exists and Kahn’s algorithm returns fewer nodes than expected. Two implementations: (1) Kahn’s BFS algorithm: initialize a queue with all nodes of in-degree 0; repeatedly dequeue a node, add to result, and decrement neighbors’ in-degrees; add any neighbor that reaches 0 to the queue. (2) DFS: after finishing all neighbors of a node, push it to a stack; the stack is the topological order in reverse. Problems requiring topological sort: Course Schedule I and II (LeetCode 207, 210), Alien Dictionary (reconstruct character order from sorted words), Task Scheduling (tasks with prerequisites), Build Systems (Maven, Make — build targets before their dependents). Recognition signal: “do X before Y” constraints on a set of tasks or nodes.”
}
}
]
}