🕸️ Graphs
Nodes + connections: build an adjacency list, then traverse (DFS/BFS), order (Kahn), group (union–find) or weigh (Dijkstra).
Recognize the pattern
Grid of land/water, pixels or rooms + count/fill regions → DFS/BFS from each unvisited cell
"Minimum steps / moves / transformations" with equal-cost moves → BFS (layer by layer)
"Nearest X" or something spreading from many places at once → multi-source BFS
Prerequisites / build order / "is it possible to finish" → topological sort (Kahn), cycle = impossible
Edges arrive one by one + "already connected?" / "which edge makes a cycle" → union–find
Weighted edges + cheapest / fastest route → Dijkstra with heapq
Build the graph
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # omit if directed
# weighted: graph[u].append((v, w))
# grid: neighbours computed on the fly
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
Grid traversal (iterative DFS)
Mark cells when you push them. An explicit stack avoids RecursionError on big grids; swap it for a deque + popleft() to get BFS.
def fill(grid: list[list[str]], r: int, c: int) -> int:
rows, cols = len(grid), len(grid[0])
stack = [(r, c)]
grid[r][c] = "#" # mark visited
size = 0
while stack:
r, c = stack.pop()
size += 1
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols
and grid[nr][nc] == "1"):
grid[nr][nc] = "#"
stack.append((nr, nc))
return size
BFS shortest path (unweighted, multi-source)
Seed the queue with one source, or with all of them for multi-source BFS.
from collections import deque
def bfs(graph, sources: list) -> dict:
dist = {s: 0 for s in sources}
queue = deque(sources)
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist: # mark on enqueue
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
Topological sort (Kahn's algorithm)
from collections import defaultdict, deque
def topo(n: int, edges: list) -> list[int]:
graph = defaultdict(list)
indeg = [0] * n
for before, after in edges:
graph[before].append(after)
indeg[after] += 1
queue = deque(i for i in range(n) if indeg[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
queue.append(nxt)
return order if len(order) == n else [] # cycle
Union–find
parent = list(range(n))
rank = [0] * n
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]] # compress
x = parent[x]
return x
def union(a: int, b: int) -> bool:
ra, rb = find(a), find(b)
if ra == rb:
return False # same group: cycle edge
if rank[ra] < rank[rb]:
ra, rb = rb, ra
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1
return True
Dijkstra (non-negative weights)
import heapq
def dijkstra(graph, src) -> dict:
dist = {src: 0}
heap = [(0, src)]
while heap:
d, node = heapq.heappop(heap)
if d > dist[node]:
continue # stale entry
for nxt, w in graph[node]:
nd = d + w
if nd < dist.get(nxt, float("inf")):
dist[nxt] = nd
heapq.heappush(heap, (nd, nxt))
return dist
Operation costs
| Operation | Time | Space |
|---|---|---|
| Build adjacency list | O(V + E) | O(V + E) |
| DFS / BFS traversal | O(V + E) | O(V) |
| Grid DFS / BFS | O(rows × cols) | O(rows × cols) |
| Topological sort (Kahn) | O(V + E) | O(V + E) |
| Union–find find / union | O(α(n)) ≈ O(1) amortised | O(n) |
| Dijkstra with heapq | O(E log V) | O(V + E) |
Watch for
Forgetting the visited set (or marking too late): cycles loop forever and BFS enqueues the same node many times.
Recursive DFS on a large grid or long chain hits Python's ~1000-deep recursion limit; use an explicit stack or BFS.
Looping over
graphkeys instead ofrange(n)misses isolated nodes with no edges.Grid bounds: check
0 <= r < rows and 0 <= c < colsbefore indexing; negative indices silently wrap around.Kahn's cycle check: if the order has fewer than n nodes, there is a cycle, so don't return a partial order.
Dijkstra: skip stale heap entries (
d > dist[node]), and never use it with negative weights.