Graph Algorithm Interview Patterns: BFS, DFS, Dijkstra, Topological Sort
Graph problems are a staple of coding interviews. The key is pattern recognition: identifying which algorithm to apply based on what the problem asks for. This guide covers the four essential graph algorithms and the exact problem types each solves.
Graph Representations
# Adjacency list (preferred for sparse graphs)
graph = defaultdict(list)
graph[0].append(1)
graph[0].append(2)
# Adjacency matrix (for dense graphs or when edge existence is the question)
matrix = [[0]*n for _ in range(n)]
matrix[0][1] = 1
# Edge list (input format for many problems)
edges = [(0,1), (1,2), (2,3)]
# Convert to adjacency list:
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # for undirectedBFS — Shortest Path in Unweighted Graph
BFS explores level by level, guaranteeing the shortest path in terms of edge count.
from collections import deque
def bfs_shortest_path(graph, start, end):
queue = deque([(start, [start])])
visited = {start}
while queue:
node, path = queue.popleft()
if node == end: return path
for nei in graph[node]:
if nei not in visited:
visited.add(nei)
queue.append((nei, path + [nei]))
return [] # no path
# Pattern: use BFS for "minimum number of steps/hops/moves"
# LeetCode: 127 Word Ladder, 1091 Shortest Path Binary Matrix, 752 Open LockDFS — Connected Components, Cycle Detection, All Paths
def dfs(graph, node, visited, result):
visited.add(node)
result.append(node)
for nei in graph[node]:
if nei not in visited:
dfs(graph, nei, visited, result)
# Count connected components:
def count_components(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v); graph[v].append(u)
visited = set()
count = 0
for i in range(n):
if i not in visited:
dfs(graph, i, visited, [])
count += 1
return count
# Cycle detection (undirected graph):
def has_cycle(graph, node, visited, parent):
visited.add(node)
for nei in graph[node]:
if nei not in visited:
if has_cycle(graph, nei, visited, node): return True
elif nei != parent: # back edge (not to direct parent) = cycle
return True
return FalseDijkstra — Shortest Path in Weighted Graph
Use when edges have non-negative weights and you need the shortest distance from one source to all nodes.
import heapq
def dijkstra(graph, src, n):
# graph[u] = [(cost, v), ...]
dist = [float('inf')] * n
dist[src] = 0
heap = [(0, src)] # (distance, node)
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue # stale entry
for cost, v in graph[u]:
if dist[u] + cost < dist[v]:
dist[v] = dist[u] + cost
heapq.heappush(heap, (dist[v], v))
return dist
# Time: O((V + E) log V) with binary heap
# Pattern: "cheapest/fastest/shortest path with weights"
# LeetCode: 743 Network Delay Time, 787 Cheapest Flights Within K Stops, 1514 Path with Max ProbabilityTopological Sort — DAG Ordering
Topological sort orders nodes in a DAG such that every edge points from earlier to later. Used for dependency resolution (build systems, course prerequisites).
# Kahn's algorithm (BFS-based):
from collections import deque
def topological_sort(n, prerequisites):
graph = defaultdict(list)
in_degree = [0] * n
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 nei in graph[node]:
in_degree[nei] -= 1
if in_degree[nei] == 0:
queue.append(nei)
return order if len(order) == n else [] # empty = cycle detected
# LeetCode: 207 Course Schedule, 210 Course Schedule II, 1203 Sort Items by GroupsUnion-Find for Graph Problems
# Faster than DFS for: connected components, cycle detection in undirected graphs
class UF:
def __init__(self, n):
self.p = list(range(n))
def find(self, x):
if self.p[x] != x: self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return False # already connected = cycle
self.p[px] = py
return True
# Redundant Connection (LeetCode 684):
def find_redundant_connection(edges):
uf = UF(len(edges) + 1)
for u, v in edges:
if not uf.union(u, v): return [u, v]Algorithm Selection Guide
| Problem Type | Algorithm |
|---|---|
| Shortest path, unweighted | BFS |
| Shortest path, non-negative weights | Dijkstra |
| Shortest path, negative weights | Bellman-Ford |
| All-pairs shortest path | Floyd-Warshall |
| Connected components | DFS or Union-Find |
| Cycle detection (undirected) | Union-Find or DFS |
| Cycle detection (directed) | DFS with color marking |
| Dependency ordering | Topological Sort (Kahn) |
| Minimum spanning tree | Kruskal (Union-Find) or Prim |
Interview Tips
- State the algorithm choice before coding: “This is shortest path in an unweighted graph, so BFS”
- For Dijkstra, always check
if d > dist[u]: continue— this handles stale heap entries - Topological sort: mention that an empty result from Kahn's means there is a cycle (used for cycle detection in directed graphs)
- Union-Find is almost always faster to code than DFS for connected component problems — use it when given a choice
- BFS state is (node, extra_state) — e.g., (node, stops_used) for Cheapest Flights Within K Stops
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When should you use BFS vs DFS for graph problems?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Use BFS when: (1) you need the shortest path in an unweighted graph – BFS explores level by level, guaranteeing the minimum number of edges; (2) level-order traversal is required; (3) the answer is near the start node (BFS finds it faster). Use DFS when: (1) you need to explore all paths or detect cycles; (2) you need connected components or topological order; (3) backtracking is involved (DFS pairs naturally with backtracking); (4) memory is a concern – DFS uses O(depth) stack space vs. BFS O(width) queue space. For a grid maze, BFS gives the shortest path. For "can you reach from A to B at all", DFS or Union-Find is equally good. When in doubt: "shortest path" -> BFS; "all paths / exhaustive exploration" -> DFS.” }
},
{
“@type”: “Question”,
“name”: “How does Dijkstra work and what is its time complexity?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Dijkstra finds the shortest path from a source to all other nodes in a weighted graph with non-negative edge weights. Algorithm: (1) initialize dist[src]=0, all others infinity; (2) use a min-heap to always process the unvisited node with the smallest current distance; (3) for each neighbor, if dist[u] + edge_weight < dist[v], update dist[v] and push (dist[v], v) to the heap; (4) skip stale heap entries with "if d > dist[u]: continue". Time complexity: O((V + E) log V) with a binary heap. Space: O(V) for distances. Does NOT work with negative weights (use Bellman-Ford). Key insight: the "if d > dist[u]: continue" check is critical – without it, a node can be processed multiple times with outdated distances.” }
},
{
“@type”: “Question”,
“name”: “How do you detect a cycle in a directed graph?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Use DFS with a three-color marking: WHITE (unvisited), GRAY (in current DFS path), BLACK (fully processed). A cycle exists if DFS encounters a GRAY node (back edge to an ancestor in the current path). Algorithm: for each unvisited node, run DFS. Mark gray when entering, black when fully done. If we reach a gray node, there is a cycle. This is the basis of Course Schedule (LeetCode 207). Alternative: Kahn's topological sort – if the sort cannot include all nodes (some remain with in-degree > 0), the graph has a cycle. For undirected graphs, use Union-Find: if union(u, v) returns False (already connected), there is a cycle.” }
}
]
}