What graph algorithms do I need to know for coding interviews?
For most coding interviews at major technology companies, you need BFS (shortest paths, level-order traversal), DFS (connectivity, cycle detection, topological sorting), Dijkstra's algorithm (weighted shortest paths), and Union-Find (disjoint set problems). Binary tree problems use a subset of graph techniques but are treated separately. Knowing when to apply each algorithm is as important as knowing the implementation.
Graph problems are among the most commonly tested topics in senior-level coding interviews, and they are frequently the questions that separate candidates who have done serious preparation from those who have not. Graphs appear everywhere in real software systems — social networks, routing algorithms, dependency resolution, network flow — so interviewers use them as a proxy for systems thinking as much as algorithmic knowledge. This guide covers the algorithms, problem types, and implementation patterns you need.
Graph Fundamentals Review
Before studying algorithms, ensure your fundamental graph concepts are solid.
Graph Terminology
Vertex (node): A fundamental unit of a graph. Edge: A connection between two vertices. Directed graph (digraph): Edges have direction. Edge (u, v) means u → v but not necessarily v → u. Undirected graph: Edges are bidirectional. Edge (u, v) means both u → v and v → u. Weighted graph: Edges have associated weights or costs. Connected graph: Every vertex is reachable from every other vertex (undirected context). Strongly connected: Every vertex is reachable from every other vertex in both directions (directed context). Cycle: A path that starts and ends at the same vertex. DAG: Directed Acyclic Graph — no cycles.
Graph Representation in Code
Adjacency list (most common in interviews):
# For undirected graph with n nodes and edges list
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # omit for directed graph
Adjacency matrix (for dense graphs or when O(1) edge lookup needed):
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
matrix[u][v] = 1
matrix[v][u] = 1 # omit for directed
Breadth-First Search (BFS)
BFS explores a graph level by level, visiting all vertices at distance d before visiting vertices at distance d+1. This property makes it the natural algorithm for shortest path problems in unweighted graphs.
BFS Implementation Template
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
# Process node here
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Time and Space Complexity
- Time: O(V + E) where V is vertices and E is edges
- Space: O(V) for the visited set and queue
BFS Use Cases in Interviews
| Problem Type | BFS Application |
|---|---|
| Shortest path (unweighted) | BFS from source; distance to each node is the level |
| Minimum number of operations | Model each state as a node; BFS finds minimum steps |
| Connected components | BFS/DFS from each unvisited node |
| Level-order tree traversal | BFS where each level is processed together |
| Bipartite graph check | BFS with two-coloring |
| Word ladder problem | BFS where each word transformation is an edge |
Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking. It is more natural than BFS for problems involving paths, cycles, and topological ordering.
DFS Implementation Template (Recursive)
def dfs(node, visited, graph):
visited.add(node)
# Process node
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor, visited, graph)
DFS Implementation Template (Iterative)
def dfs_iterative(graph, start):
visited = set([start])
stack = [start]
while stack:
node = stack.pop()
# Process node
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
DFS Use Cases in Interviews
| Problem Type | DFS Application |
|---|---|
| Cycle detection (directed) | DFS with three states: unvisited, in-progress, complete |
| Cycle detection (undirected) | DFS tracking parent to avoid false cycles |
| Topological sort | DFS post-order; reverse gives topological order |
| Number of islands | Grid DFS marking visited cells |
| Path finding | DFS with backtracking |
| Strongly connected components | Kosaraju's or Tarjan's algorithm |
Cycle Detection
Cycle detection is a standalone interview question and also a subproblem in many other problems.
Cycle Detection in Undirected Graphs (DFS)
Track the parent of each node. If you encounter a neighbor that is visited and is not the parent, you have found a cycle.
Cycle Detection in Directed Graphs (DFS Coloring)
Use three states: 0 = unvisited, 1 = in current DFS path, 2 = fully processed. If you encounter a node with state 1, you have found a cycle.
def has_cycle_directed(graph, n):
state = [0] * n
def dfs(node):
state[node] = 1 # in progress
for neighbor in graph[node]:
if state[neighbor] == 1:
return True # cycle found
if state[neighbor] == 0:
if dfs(neighbor):
return True
state[node] = 2 # fully processed
return False
return any(dfs(node) for node in range(n) if state[node] == 0)
Topological Sort
Topological sorting of a directed acyclic graph produces a linear ordering of vertices such that for every edge (u, v), u appears before v. This is used for dependency resolution, build order problems, and course scheduling.
Kahn's Algorithm (BFS-based)
Compute in-degree of all nodes. Add all zero-in-degree nodes to a queue. Process queue: take a node, add it to the result, reduce in-degrees of neighbors; add any that become zero-in-degree to the queue.
DFS Post-Order Approach
Run DFS. When a node finishes (all neighbors processed), add it to a stack. The topological order is the reverse of the finish order.
Interview recognition: If the problem mentions "prerequisites," "dependencies," "build order," or "course schedule" — topological sort.
Dijkstra's Algorithm
Dijkstra's finds shortest paths from a source to all other vertices in a weighted graph with non-negative edge weights.
Implementation with Min-Heap
import heapq
def dijkstra(graph, start, n):
dist = [float('inf')] * n
dist[start] = 0
heap = [(0, start)] # (distance, node)
while heap:
d, node = heapq.heappop(heap)
if d > dist[node]:
continue # outdated entry
for neighbor, weight in graph[node]:
new_dist = dist[node] + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return dist
Complexity: O((V + E) log V) with a binary min-heap.
Union-Find (Disjoint Set Union)
Union-Find maintains a collection of disjoint sets and supports two operations efficiently: finding which set a node belongs to, and merging two sets.
Applications in Interviews
- Detecting cycles in undirected graphs
- Minimum spanning tree (Kruskal's algorithm)
- Number of connected components
- Dynamic connectivity problems
Implementation with Path Compression and Union by Rank
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):
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
return True
Complexity: Near O(1) per operation with path compression and union by rank.
Common Graph Interview Problems by Algorithm
| Problem | Algorithm | Key Insight |
|---|---|---|
| Number of Islands | DFS/BFS | Grid as implicit graph |
| Course Schedule (cycle detection) | DFS coloring | Directed graph cycle |
| Course Schedule II (ordering) | Topological sort | Kahn's or DFS post-order |
| Network Delay Time | Dijkstra | Weighted shortest path |
| Cheapest Flight Within K Stops | Modified BFS/Bellman-Ford | BFS with state (node, stops_remaining) |
| Pacific Atlantic Water Flow | BFS/DFS from both borders | Reverse direction thinking |
| Clone Graph | BFS + hash map | Track visited nodes with new nodes |
| Word Ladder | BFS + neighbor generation | State = current word |
| Redundant Connection | Union-Find | Find first edge that creates cycle |
| Accounts Merge | Union-Find | Group accounts by shared email |
Frequently Asked Questions
When should I use BFS vs. DFS for graph problems? Use BFS when you need shortest paths, minimum steps, or level-by-level information. Use DFS when you need to explore all paths, detect cycles, perform topological ordering, or when the problem has a backtracking nature. For connected components and island counting, both work equally well — DFS is typically simpler to implement recursively.
Do I need to know Bellman-Ford and Floyd-Warshall for interviews? Bellman-Ford (handles negative edges) and Floyd-Warshall (all-pairs shortest path) are less commonly required but appear in some interview loops at top companies. Know the key properties: Bellman-Ford runs in O(VE) and can detect negative cycles; Floyd-Warshall runs in O(V³) and finds all-pairs shortest paths. If your interview is at a company known for hard algorithmic problems, study these.
How do I handle grid problems — are they graph problems? Yes. In grid problems, each cell is a node and edges exist between adjacent cells (typically 4-directional or 8-directional). BFS and DFS on grids follow the same patterns as on explicit graphs. The main difference is how you represent neighbors (using dx/dy offsets) rather than an adjacency list.
References
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed., Chapters 22-24). MIT Press.
- Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed., Part 4: Graphs). Addison-Wesley Professional.
- Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed., Chapter 5). Springer.
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
- Gayle Laakmann McDowell. (2015). Cracking the Coding Interview (6th ed., Chapter 4: Trees and Graphs). CareerCup.