Algorithms - graph traversal patterns

Almost every system at scale has a graph hiding in it — service dependencies, permission models, routing, social networks. Knowing the canonical traversals, and which one matches which question, is the lead-engineer skill.

Representations

• Adjacency list — {node: [neighbors]}. Default for sparse graphs. O(V+E) space.
• Adjacency matrix — M[i][j] = weight. O(V²) space, O(1) edge query. Use when graph is dense or when you’ll repeatedly ask “is there an edge.”
• Edge list — [(u, v, w), ...]. Good for Kruskal / batch processing; useless for traversal without preprocessing.

The four traversals worth memorizing

Algorithm	Use for	Cost	Notes
BFS	Shortest path in unweighted graph	O(V+E)	Layer-by-layer; queue
DFS	Connectivity, cycle detection, topo sort, SCC	O(V+E)	Stack or recursion; watch stack depth
Dijkstra	Shortest path, non-negative weights	O((V+E) log V)	Min-heap by tentative distance
Bellman–Ford	Shortest path, negative weights	O(V·E)	Detects negative cycles

A* is Dijkstra + heuristic; useful when you have a domain estimate (Euclidean distance for grids).

Pattern recognition

• “Shortest moves to…” on a grid or unweighted graph → BFS.
• “Minimum cost path / network delay / cheapest flight” → Dijkstra. Watch for “at most k stops” — that turns it into Bellman-Ford-like or BFS-with-state.
• “Can we reach / how many islands / connected components” → DFS or union-find.
• “Order of execution given dependencies” → topological sort (Kahn’s algorithm or DFS post-order).
• “Cycle in directed graph” → DFS with WHITE/GRAY/BLACK colors, or Kahn’s terminating with leftover nodes.
• “MST” → Prim (heap-based, dense) or Kruskal (sort + union-find, sparse).
• “Word ladder / state-space search” → BFS over implicit graph; build neighbors lazily via patterns or transformations.

Multi-source BFS

When multiple starting points all expand simultaneously (rotting oranges, gates and walls): push all sources to the queue first, then run standard BFS. The traversal is correct because BFS expands by distance from the source set as a whole. Often mistaken for needing DP.

Lazy deletion in heap-based algorithms

Dijkstra/Prim with a heap and updates: don’t decrease-key. Instead, push a new (cost, node) and skip stale entries:

while heap:
    cost, node = heappop(heap)
    if node in visited: continue
    visited.add(node)
    for nbr, w in graph[node]:
        if nbr not in visited:
            heappush(heap, (cost + w, nbr))

Cleaner than a real decrease-key for any practical scale.

Union-find (DSU)

Two operations: find(x) (with path compression) and union(x, y) (with rank). Effectively O(α(n)) per op. Reach for it for:

• Connected components in dynamic graphs.
• Detecting cycle in undirected graph (edge connects two nodes already in same component).
• Kruskal’s MST.
• Equivalence classes (account merging, friend groups).