Graph Algorithms for Interviews: The Essential Cheatsheet
BFS, DFS, Dijkstra, topological sort, union-find — everything you need to know about graph algorithms for coding interviews.
Here is the enhanced blog post with code examples and additional depth:
Graph problems show up in many forms -- grid traversal, social networks, dependency resolution, shortest paths -- but the underlying algorithms are a small, learnable set. This cheatsheet covers every graph concept you need for interviews.
Graph Representation
Adjacency list is the default for interviews. Use a hash map where each key is a node and the value is a list of neighbors. O(V + E) space. This representation is efficient for sparse graphs and makes iterating through neighbors straightforward.
Adjacency matrix uses a 2D array. O(V²) space. Only practical for small, dense graphs. The matrix allows O(1) edge existence checks but requires O(V) time to list all neighbors of a node.
Implicit graphs are common. Grid problems (like Number of Islands) treat each cell as a node with edges to adjacent cells. You don't need to build an explicit graph structure—just traverse the grid directly.
Here's how to implement adjacency list representation in different languages:
# Adjacency list representation for an undirected graph
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = {i: [] for i in range(num_vertices)}
def add_edge(self, u, v):
self.adj_list[u].append(v)
self.adj_list[v].append(u) # For undirected graph
def print_graph(self):
for vertex in range(self.num_vertices):
print(f"{vertex}: {self.adj_list[vertex]}")
# Usage
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.print_graph()
BFS: Breadth-First Search
BFS explores nodes level by level using a queue. Use it for shortest path in unweighted graphs and level-order traversal. BFS guarantees that when you first visit a node, you've found the shortest path to it in terms of number of edges.
Template: Initialize a queue with the starting node(s), mark as visited, then process each node by adding unvisited neighbors. Track distance by processing level by level. For level tracking, you can either use a distance array or process nodes level by level with a nested loop.
Key problems: Word Ladder, Rotting Oranges (multi-source BFS), Shortest Path in Binary Matrix.
Here's a complete BFS implementation:
from collections import deque
def bfs(graph, start):
"""Standard BFS traversal returning visited nodes in BFS order."""
visited = set()
result = []
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
# Example usage with adjacency list
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1],
5: [2]
}
print("BFS traversal starting from node 0:", bfs(graph, 0))
DFS: Depth-First Search
DFS explores as deep as possible before backtracking, using recursion or an explicit stack. Use it for cycle detection, connected components, topological sorting, and path exploration. DFS is naturally recursive and is excellent for exploring all possible paths.
Template: Mark the current node as visited, then recursively visit each unvisited neighbor. For cycle detection in directed graphs, maintain a "currently in stack" set alongside the visited set. This helps detect back edges in directed graphs.
Key problems: Number of Islands, Clone Graph, Course Schedule, Pacific Atlantic Water Flow.
Here's DFS implementation with both recursive and iterative approaches:
def dfs_recursive(graph, node, visited=None, result=None):
"""Recursive DFS implementation."""
if visited is None:
visited = set()
if result is None:
result = []
visited.add(node)
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited, result)
return result
def dfs_iterative(graph, start):
"""Iterative DFS implementation using a stack."""
visited = set()
result = []
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
result.append(node)
# Add neighbors in reverse to maintain similar order to recursive
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return result
# Example usage
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1],
5: [2]
}
print("Recursive DFS:", dfs_recursive(graph, 0))
print("Iterative DFS:", dfs_iterative(graph, 0))
BFS vs DFS
Use BFS for shortest distance, minimum steps, or level-by-level processing. Use DFS for connected components, cycle detection, or path existence. For reachability alone, either works.
Practical considerations:
- BFS uses more memory (queue size can be O(V) in worst case)
- DFS uses less memory (stack depth is O(V) in worst case for recursive, but typically less)
- BFS finds the shortest path in unweighted graphs
- DFS is easier to implement recursively for tree-like exploration
Topological Sort
Produces a linear ordering of nodes in a DAG such that every edge goes from earlier to later. Standard for dependency resolution. Topological sort only exists for Directed Acyclic Graphs (DAGs).
Kahn's Algorithm (BFS-based): Compute in-degrees, enqueue all nodes with in-degree 0, process each by decrementing neighbors' in-degrees, enqueue any that hit 0. This algorithm is intuitive and works well when you need to detect cycles.
DFS-based: Run DFS and push nodes onto a stack in post-order. Reverse for topological order. This approach is more natural if you're already doing DFS for other purposes.
Key problems: Course Schedule, Course Schedule II, Alien Dictionary.
Here's both implementations:
from collections import deque
def topological_sort_kahn(num_courses, prerequisites):
"""Kahn's algorithm for topological sort."""
# Build graph and in-degree array
graph = {i: [] for i in range(num_courses)}
in_degree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
# Initialize queue with nodes having 0 in-degree
queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# Check if topological sort exists (graph is DAG)
if len(result) == num_courses:
return result
return [] # Cycle detected
def topological_sort_dfs(num_courses, prerequisites):
"""DFS-based topological sort."""
# Build graph
graph = {i: [] for i in range(num_courses)}
for course, prereq in prerequisites:
graph[prereq].append(course)
visited = [0] * num_courses # 0=unvisited, 1=visiting, 2=visited
result = []
def dfs(node):
if visited[node] == 1: # Cycle detected
return False
if visited[node] == 2: # Already processed
return True
visited[node] = 1 # Mark as visiting
for neighbor in graph[node]:
if not dfs(neighbor):
return False
visited[node] = 2 # Mark as visited
result.append(node)
return True
for i in range(num_courses):
if visited[i] == 0:
if not dfs(i):
return [] # Cycle detected
return result[::-1] # Reverse to get topological order
# Example usage
num_courses = 6
prerequisites = [[1, 0], [2, 1], [3, 1], [4, 2], [5, 3]]
print("Kahn's algorithm:", topological_sort_kahn(num_courses, prerequisites))
print("DFS-based:", topological_sort_dfs(num_courses, prerequisites))
Dijkstra's Algorithm
Finds the shortest path in a weighted graph with non-negative edges. Uses a min-heap to always process the closest unvisited node. Dijkstra's algorithm is greedy and works by repeatedly selecting the vertex with the smallest known distance from the source.
Template: Initialize distances to infinity except the source (0). Push source into a min-heap. Pop the smallest, skip if processed, and relax all edges. The relaxation step checks if going through the current node provides a shorter path to its neighbors.
Key problems: Network Delay Time, Cheapest Flights Within K Stops, Path with Minimum Effort.
Here's Dijkstra's algorithm implementation:
import heapq
def dijkstra(graph, start):
"""Dijkstra's algorithm for shortest paths in weighted graphs."""
# Initialize distances
distances = {node: float('inf') for node in graph}
distances[start] = 0
# Priority queue: (distance, node)
pq = [(0, start)]
while pq:
current_dist, current_node = heapq.heappop(pq)
# Skip if we found a better path already
if current_dist > distances[current_node]:
continue
# Relax edges
for neighbor, weight in graph[current_node]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
# Example usage: weighted graph as adjacency list
graph = {
0: [(1, 4), (2, 1)],
1: [(3, 1)],
2: [(1, 2), (3, 5)],
3: [(4, 3)],
4: []
}
print("Shortest distances from node 0:", dijkstra(graph, 0))
Union-Find (Disjoint Set Union)
Tracks connected components with near-O(1) find and union operations using path compression and union by rank. Union-Find is particularly useful for dynamic connectivity problems where edges are added over time.
When to use: Dynamically tracking components as edges are added, repeated connectivity queries, minimum spanning tree (Kruskal's). The two key optimizations are path compression (flattening the tree during find operations) and union by rank (attaching smaller trees to larger ones).
Key problems: Number of Provinces, Redundant Connection, Accounts Merge.
Here's a complete Union-Find implementation:
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.components = n
def find(self, x):
"""Find with path compression."""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""Union by rank."""
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # Already connected
# Union by rank
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
self.components -= 1
return True
def connected(self, x, y):
"""Check if x and y are in the same component."""
return self.find(x) == self.find(y)
def count_components(self):
"""Return the number of connected components."""
return self.components
# Example usage
uf = UnionFind(5)
print("Initial components:", uf.count_components())
uf.union(0, 1)
uf.union(1, 2)
uf.union(3, 4)
print("After unions:")
print("Are 0 and 2 connected?", uf.connected(0, 2))
print("Are 0 and 3 connected?", uf.connected(0, 3))
print("Components:", uf.count_components())