Graph algorithms — BFS, DFS, topological sort, union-find
Representation
# Adjacency list — most common
graph = {
"a": ["b", "c"],
"b": ["c", "d"],
"c": ["d"],
"d": [],
}
# Or as defaultdict for dynamic building:
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # for undirectedFor dense graphs or weighted graphs, sometimes adjacency matrix or list of (weight, neighbor) tuples.
BFS — shortest path in unweighted graph
from collections import deque
def bfs_shortest_path(graph, start, target):
if start == target: return 0
visited = {start}
q = deque([(start, 0)])
while q:
node, dist = q.popleft()
for n in graph[node]:
if n == target:
return dist + 1
if n not in visited:
visited.add(n)
q.append((n, dist + 1))
return -1BFS on an unweighted graph gives shortest path in O(V+E). For weighted graphs, use Dijkstra (see weighted file).
DFS — recursive
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for n in graph[start]:
if n not in visited:
dfs(graph, n, visited)
return visitedFor deep graphs, convert to iterative with an explicit stack to avoid recursion-depth issues.
Pattern: connected components
def count_components(graph):
visited = set()
count = 0
for node in graph:
if node not in visited:
count += 1
stack = [node]
while stack:
n = stack.pop()
if n in visited: continue
visited.add(n)
stack.extend(graph[n])
return countTopological sort (Kahn’s algorithm — BFS-based)
For DAGs (directed acyclic graphs). Order nodes so every edge u→v has u before v.
from collections import defaultdict, deque
def topological_sort(num_nodes, edges):
graph = defaultdict(list)
in_degree = [0] * num_nodes
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
q = deque(i for i in range(num_nodes) if in_degree[i] == 0)
order = []
while q:
node = q.popleft()
order.append(node)
for n in graph[node]:
in_degree[n] -= 1
if in_degree[n] == 0:
q.append(n)
if len(order) != num_nodes:
return None # cycle detected
return orderUse cases: course scheduling, build dependencies, package install order. Cycle detection is free — if the result has fewer nodes than the input, there was a cycle.
DFS-based topological sort (post-order reversed)
def topo_dfs(graph):
visited = set()
on_stack = set()
order = []
def visit(node):
if node in on_stack:
raise ValueError("cycle")
if node in visited:
return
on_stack.add(node)
for n in graph[node]:
visit(n)
on_stack.discard(node)
visited.add(node)
order.append(node)
for node in graph:
if node not in visited:
visit(node)
return order[::-1]Same complexity (O(V+E)). Choose Kahn’s for cycle detection clarity; DFS-based when you’re already doing DFS for other reasons.
Union-Find (Disjoint Set Union)
For dynamic connectivity / “are these in the same group” queries. Operations: find(x), union(x, y). With path compression and union by rank: nearly O(1) per operation (amortized α(n)).
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x: int) -> int:
root = x
while self.parent[root] != root:
root = self.parent[root]
# Path compression
while self.parent[x] != root:
self.parent[x], x = root, self.parent[x]
return root
def union(self, x: int, y: int) -> bool:
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # already in same set
# Union by rank
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return TrueUse cases: Kruskal’s MST, dynamic connectivity, “number of provinces”, “redundant connection” detection.
Problem: number of islands
def num_islands(grid):
if not grid: return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "1":
return
grid[r][c] = "0" # mark visited
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
dfs(r + dr, c + dc)
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
count += 1
dfs(r, c)
return countGrids are graphs in disguise. Each cell connects to its 4 (or 8) neighbors.
Problem: course schedule (cycle detection)
def can_finish(num_courses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * num_courses
for c, p in prerequisites:
graph[p].append(c)
in_degree[c] += 1
q = deque(i for i in range(num_courses) if in_degree[i] == 0)
completed = 0
while q:
course = q.popleft()
completed += 1
for next_ in graph[course]:
in_degree[next_] -= 1
if in_degree[next_] == 0:
q.append(next_)
return completed == num_coursesTopological sort with cycle detection.
Pitfalls
- Forgetting to mark visited before recursing — leads to revisits and stack overflow.
- BFS without visited set on cyclic graphs — infinite loop.
- DFS on adjacency matrix vs list — matrix is O(V²) per node visit.
- Mutating the input grid as a “visited marker” — fine, but document it.
- Off-by-one in BFS distance: distance to start is 0, not 1.
Interview angle
- “How do you detect a cycle in a graph?” - directed: DFS with three colours (unvisited, in-progress, done), where an edge to an in-progress node is a back edge and therefore a cycle. Undirected: DFS tracking the parent, or union-find where an edge joining two nodes already in the same set closes a cycle.
- “What is topological sort for, and when is it impossible?” - ordering with dependencies: build systems, task scheduling, course prerequisites. It exists only for a DAG, so if Kahn’s algorithm finishes with nodes remaining, the graph has a cycle. That’s the standard cycle test.
- “Kahn’s or DFS-based topological sort?” - Kahn’s (repeatedly remove in-degree-zero nodes) detects cycles naturally and is easier to explain; the DFS version pushes nodes on finish and reverses. Both
O(V+E). - “When is union-find the right structure?” - dynamic connectivity and grouping: Kruskal’s MST, counting connected components, detecting cycles as you add edges. With path compression and union by rank it’s effectively
O(1)amortised per operation.