Why Graph Algorithms Matter in Interviews
Graph problems appear constantly in technical interviews because they model real systems: social networks (friend-of-friend), maps and routing (shortest path), dependency resolution (topological sort), and network connectivity (union-find). The key is recognizing which algorithm to apply: BFS for shortest paths in unweighted graphs, DFS for cycle detection and connected components, Dijkstra for weighted shortest paths, and topological sort for dependency ordering.
Pattern 1: BFS for Shortest Path
Use BFS when edge weights are uniform (or 1). BFS explores nodes level by level — the first time you reach the target, it’s via the shortest path.
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 neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # no path exists
# Applications: word ladder, maze solving, shortest path in unweighted graph
Pattern 2: DFS for Cycle Detection
Use DFS with three states: WHITE (unvisited), GRAY (in current DFS path), BLACK (fully processed). A back edge to GRAY = cycle.
def has_cycle_directed(graph):
WHITE, GRAY, BLACK = 0, 1, 2
color = {node: WHITE for node in graph}
def dfs(node):
color[node] = GRAY
for neighbor in graph[node]:
if color[neighbor] == GRAY:
return True # back edge = cycle
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[node] = BLACK
return False
return any(dfs(node) for node in graph if color[node] == WHITE)
Pattern 3: Topological Sort (Kahn’s Algorithm)
For DAGs (directed acyclic graphs): order nodes so every edge goes from earlier to later. Used for: build systems, course prerequisites, task scheduling.
from collections import deque, defaultdict
def topological_sort(n, edges):
# edges = [(0,1), (0,2), (1,3), (2,3)] (prerequisite -> course)
in_degree = [0] * n
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
in_degree[v] += 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 adj[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == n else [] # empty = cycle exists
Pattern 4: Dijkstra’s Algorithm
Shortest path in weighted graphs (non-negative weights). Use a min-heap to always expand the cheapest unvisited node.
import heapq
def dijkstra(graph, start):
# graph[u] = [(weight, v), ...]
dist = {node: float('inf') for node in graph}
dist[start] = 0
heap = [(0, start)] # (cost, node)
while heap:
cost, node = heapq.heappop(heap)
if cost > dist[node]:
continue # stale entry
for weight, neighbor in graph[node]:
new_cost = cost + weight
if new_cost < dist[neighbor]:
dist[neighbor] = new_cost
heapq.heappush(heap, (new_cost, neighbor))
return dist
Time complexity: O((V + E) log V). Cannot handle negative edge weights — use Bellman-Ford instead.
Pattern 5: Union-Find for Connected Components
Efficiently track connected components with path compression and union by rank. Each element points to a root; two elements are connected if they share a root.
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 True
# Applications: number of islands II, accounts merge, redundant connections
Algorithm Selection Guide
| Problem | Algorithm | Complexity |
|---|---|---|
| Shortest path, unweighted | BFS | O(V+E) |
| Shortest path, weighted | Dijkstra | O((V+E) log V) |
| Shortest path, negative weights | Bellman-Ford | O(VE) |
| All-pairs shortest path | Floyd-Warshall | O(V³) |
| Cycle detection (directed) | DFS (3-color) | O(V+E) |
| Topological ordering | Kahn’s BFS | O(V+E) |
| Connected components | Union-Find | O(α(N)) per op |
| Minimum spanning tree | Kruskal/Prim | O(E log E) |
Key Interview Tips
- BFS vs DFS: BFS for shortest path, DFS for exhaustive search and cycle detection
- Always check for disconnected graphs — iterate over all nodes to start DFS/BFS
- Topological sort can also detect cycles: if output length < n, a cycle exists
- Union-Find is O(α(n)) ≈ O(1) amortized — prefer it over BFS/DFS for repeated connectivity queries
- Grid problems are graph problems: cells are nodes, adjacent cells are edges
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”When should I use BFS vs DFS for graph problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use BFS when you need the shortest path in an unweighted graph — BFS explores level by level, so the first time you reach the target is via the fewest edges. Use DFS when you need to explore all possibilities (cycle detection, connected components, topological sort, backtracking). A helpful heuristic: if the problem asks "minimum steps" or "shortest distance," think BFS first. If it asks "can we reach X" or "list all paths," think DFS.”}},{“@type”:”Question”,”name”:”How does Dijkstra’s algorithm work and what are its limitations?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Dijkstra uses a min-heap to always expand the unvisited node with the lowest known distance from the source. For each expanded node, it relaxes all outgoing edges: if dist[node] + edge_weight < dist[neighbor], update dist[neighbor] and push to the heap. Time complexity: O((V+E) log V). Limitation: cannot handle negative edge weights — a negative edge can make a previously-optimal path worse in hindsight, which Dijkstra’s greedy approach misses. Use Bellman-Ford for graphs with negative weights.”}},{“@type”:”Question”,”name”:”How does topological sort work and when do you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Topological sort orders nodes in a DAG so every directed edge u→v has u before v. Kahn’s algorithm: (1) Compute in-degree for all nodes. (2) Start with all nodes having in-degree 0. (3) Process each zero-in-degree node, add to output, decrement neighbors’ in-degrees. (4) Add newly zero-in-degree nodes to the queue. If output length < n, the graph has a cycle. Use cases: course prerequisites (can you finish all courses?), build dependency order, task scheduling.”}},{“@type”:”Question”,”name”:”How does Union-Find detect if adding an edge creates a cycle?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Before adding edge (u, v): call find(u) and find(v). If they return the same root, u and v are already in the same component — adding this edge creates a cycle. If different roots, call union(u, v) to merge the components and add the edge safely. This is used in Kruskal’s minimum spanning tree algorithm: process edges by weight; add each edge only if it doesn’t create a cycle (different components). Union-Find with path compression and union-by-rank is nearly O(1) per operation.”}},{“@type”:”Question”,”name”:”How do you detect a cycle in a directed vs undirected graph?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Directed graph: use DFS with 3 colors — WHITE (unvisited), GRAY (in current recursion stack), BLACK (done). A back edge to a GRAY node = cycle. Equivalently, topological sort returns fewer nodes than total if a cycle exists. Undirected graph: during DFS, if you reach a visited node that is not the parent of the current node, it’s a cycle. Or use Union-Find: if both endpoints of an edge are already in the same component, adding it creates a cycle.”}}]}
Graph algorithm patterns are commonly tested at Google coding interview questions.
BFS, DFS, Dijkstra, and topological sort patterns appear in Meta coding interview preparation.
Graph traversal and shortest path problems are tested in Amazon coding interview guide.