Most graph problems in interviews never use the word “graph.” They talk about courses with prerequisites, a grid of islands, a network of servers going down, a pile of accounts that need merging. The first skill is noticing a graph is hiding in the prompt. The second is matching the wording to one of roughly five algorithms, because almost every graph question a company asks is a thin wrapper around BFS, DFS, topological sort, union-find, or Dijkstra.
Once you can name the algorithm from the phrasing, the coding part is mostly mechanical. What separates a clean solve from a stall is knowing the small gotchas that quietly break each template.
Spotting the graph before you pick the algorithm
A graph is just nodes and edges. Whenever a problem gives you things and relationships between them, you probably have one. Cities and flights. People and friendships. Files and imports. Tasks and dependencies. Grid cells and their neighbors. The moment you see “connected,” “reachable,” “shortest,” “cycle,” “order,” or “group,” a graph interpretation is likely the intended one.
Grids trip people up because they don’t look like graphs. A 2D matrix where you can step up, down, left, and right is a graph where each cell is a node with up to four edges. Number of Islands, Rotting Oranges, and Walls and Gates are all grid problems that reduce to a plain traversal once you treat neighbors as edges. You rarely build an explicit adjacency list for a grid; you compute neighbors on the fly from the coordinates.
For non-grid inputs you usually build an adjacency list first: a dict from node to its list of neighbors. That short preprocessing step is where a surprising number of candidates fumble under pressure, so practice it until it’s automatic.
BFS when you need the fewest steps
Breadth-first search explores in rings: all nodes one step away, then two steps, and so on. That layering is exactly what you want for the shortest path in an unweighted graph, because the first time BFS reaches a node, it has reached it by the fewest edges possible. Word Ladder, shortest path in a binary maze, and “minimum moves” puzzles are all BFS.
The template for a grid is short:
from collections import deque
def shortest_path(grid, start, target):
rows, cols = len(grid), len(grid[0])
q = deque([(start, 0)])
seen = {start}
while q:
(r, c), dist = q.popleft()
if (r, c) == target:
return dist
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in seen:
seen.add((nr, nc))
q.append(((nr, nc), dist + 1))
return -1Two details matter. Mark a node as seen when you enqueue it, not when you dequeue it, or the same cell lands in the queue several times and the runtime blows up. And when a problem starts from many sources at once, like fire spreading or oranges rotting, push all the starting cells into the queue before the loop begins. That multi-source trick turns a lot of “how many minutes until everything is X” questions into a single BFS.
DFS for connectivity, cycles, and flood fill
Depth-first search goes as deep as it can down one path before backing up. It’s the tool for questions that ask whether things are connected, how many separate groups exist, or whether a cycle exists. Counting islands is DFS (or BFS, either works) where each unvisited land cell kicks off a traversal that paints its whole component. Flood fill in an image editor is the same shape.
DFS also detects cycles, though the bookkeeping differs by graph type. In an undirected graph, a cycle means you reached an already-visited node that isn’t the one you just came from. In a directed graph you need three states per node (unvisited, in-progress, done), and a cycle is an edge back to a node still marked in-progress. That directed version is what the Course Schedule problem is really testing, and it’s a common setup for the follow-up phrased as “give me a valid order.”
Recursion depth is the practical risk. On a graph with a hundred thousand nodes in a line, recursive DFS can hit Python’s recursion limit, so mention that you’d switch to an explicit stack for very deep inputs. Interviewers like hearing that you know the failure mode before you hit it.
Topological sort when the problem is really about order
Any prompt about prerequisites, build order, task scheduling, or what has to happen before what is asking for a topological sort of a directed acyclic graph. Course Schedule II, Alien Dictionary, and build-system ordering are the classics.
Kahn’s algorithm is the version most people reach for because it detects impossibility for free. Compute the in-degree of every node, start a queue with the nodes that have in-degree zero, and repeatedly remove a node and decrement its neighbors’ in-degrees. If you process fewer nodes than the graph contains, there’s a cycle and no valid order exists. The DFS variant works too: run DFS and prepend each node to the answer as it finishes, which gives you a reverse postorder.
Alien Dictionary is the one that separates people. You’re given words sorted in an unknown alphabet and asked for the letter order. The trick is that comparing two adjacent words gives you exactly one edge, the first position where they differ, and then it’s a straight topological sort. Candidates who jump to code before building the graph almost always miss the edge cases, like a longer word appearing before its own prefix, which is invalid input.
Union-Find for “are these two connected” at scale
Union-Find, also called disjoint set union, answers one thing fast: are these two nodes in the same group, and merge two groups when they aren’t. It wins when the graph is changing, edges arrive one at a time, and you’re repeatedly asked about connectivity. Number of Connected Components, Redundant Connection, and Accounts Merge are textbook union-find.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path compression
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already connected: this edge closes a cycle
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return TrueWith path compression and union by rank, each operation is effectively constant time. The union returning False is the cycle-detection signal: if two endpoints already share a root, the new edge closes a loop. That single line solves Redundant Connection and is the pruning check inside Kruskal’s minimum spanning tree algorithm.
Dijkstra and its neighbors when edges have weights
BFS gives shortest paths only when every edge costs the same. Once edges carry different weights (distances, times, prices) you need Dijkstra, which uses a min-heap to always expand the cheapest node reached so far. Network Delay Time, Cheapest Flights Within K Stops, and Path With Minimum Effort are the usual suspects.
import heapq
def dijkstra(graph, src, n):
dist = [float('inf')] * n
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(heap, (dist[v], v))
return distSkip the stale-entry check (if d > dist[u]: continue) and the heap fills with outdated pairs; keep it and the runtime stays O(E log V). Two variations show up often enough to name. If some edge weights are negative, Dijkstra breaks and you want Bellman-Ford, which also detects negative cycles. If every edge weight is either 0 or 1, a deque-based 0-1 BFS beats Dijkstra by pushing zero-weight neighbors to the front of the deque and one-weight neighbors to the back.
Reading the signal in one place
The mapping from problem wording to algorithm is worth memorizing as a single table, because the interview clock rewards recognizing the pattern in the first minute.
| What the problem asks for | Algorithm to reach for | Typical time complexity | Example question |
|---|---|---|---|
| Fewest steps or moves in an unweighted graph or grid | BFS | O(V + E) | Word Ladder, Rotting Oranges |
| Count groups, flood fill a region, or detect any cycle | DFS | O(V + E) | Number of Islands, Course Schedule |
| Order tasks under prerequisites (directed, acyclic) | Topological sort (Kahn or DFS) | O(V + E) | Course Schedule II, Alien Dictionary |
| Merge groups repeatedly, test dynamic connectivity, or find an undirected cycle | Union-Find (DSU) | Near O(1) per operation | Accounts Merge, Redundant Connection |
| Shortest path with non-negative edge weights | Dijkstra (min-heap) | O(E log V) | Network Delay Time, Cheapest Flights Within K Stops |
| Shortest path where some edge weights are negative | Bellman-Ford | O(V × E) | Cheapest path with rebates or penalties |
| Shortest path where every edge weight is 0 or 1 | 0-1 BFS (deque) | O(V + E) | Minimum Obstacle Removal to Reach Corner |
What interviewers actually push on
Naming the algorithm gets you maybe half the score. The rest is what you say around it. State the time and space complexity in terms of V and E before you’re asked; graph solutions are almost always O(V + E) for plain traversal and O(E log V) for Dijkstra, and getting that wrong reads as a red flag. Talk about how you’d handle a disconnected graph, since a single BFS from one node misses whole components, and plenty of candidates forget to loop over every unvisited node.
Company flavors are real. Amazon leans on shortest-path and dependency questions that mirror delivery routing and package builds. Meta asks a lot of connectivity and BFS-on-a-social-graph problems, friend recommendations being the obvious one. Microsoft likes cycle detection and problems that fold neatly into union-find. None of that changes the five templates; it changes which one you should expect and how the story is dressed up.
The strongest candidates rarely rely on having memorized twenty problems. They hear “prerequisites” and think toposort, hear “cheapest with weights” and think Dijkstra, hear “keep merging groups” and think union-find, and they write the template cleanly while calling out the two or three gotchas that break it. Build that mapping from wording to algorithm and most graph rounds stop being scary.
Drill the patterns next:
