Graphs — How the Pattern Works
Graph algorithms model entities as vertices V and pairwise relationships as directed, undirected, or weighted edges E, typically stored in an O(V + E) adjacency list for O(1) neighbor iteration per edge. Rather than enumerating exponentially many simple paths or state permutations in O(2^V) or O(V!) time, graph traversals maintain a monotonic frontier and a visited (or optimal-cost) invariant so each vertex or augmented (vertex, progress) state is processed once. Selecting the frontier structure that matches edge weights—a FIFO queue for unit-cost BFS in O(V + E), a deque for binary {0, 1} weights in O(V + E), a priority queue for non-negative weights via Dijkstra in O(E log V), or recursive DFS with memoization—yields optimal reachability, shortest paths, and cycle detection.
- Input specifies entities and pairwise links (edge lists, adjacency lists, flight tickets, transit routes, or trust pairs) or an m x n grid with 4-directional adjacency, asking for reachability, connected component sizes, or cycle lengths.
- Minimum-cost or shortest-path queries where every step costs 1 (unweighted BFS), moves cost either 0 or 1 (0-1 BFS on a deque), or edges carry non-negative additive times or multiplicative probabilities (Dijkstra on a heap).
- Shortest-path problems coupled with an auxiliary budget or subset goal—such as eliminating at most k obstacles or visiting all n <= 12 vertices—where lifting the state to (vertex, remaining_k) or (vertex, bitmask) makes transitions unweighted.
- Structural graph questions decidable via degree invariants, edge-count theorems, or post-order exhaustion, such as tree validation (len(edges) == n - 1 plus connectivity), finding a universal sink/judge (in_degree - out_degree == n - 1), or Eulerian itinerary reconstruction (Hierholzer's algorithm).
- Marking vertices visited upon popping from the BFS queue instead of upon enqueuing: delaying the visited mark lets multiple neighbors in the current frontier enqueue duplicate copies of the same vertex, inflating queue memory and runtime.
- Keying visited only on vertex coordinates during budgeted or subset-visiting BFS: if an early path reaches (r, c) with 0 obstacle removals left and marks (r, c) visited, it blocks a slightly longer path arriving with spare removals needed to breach a later wall.
- Recording cloned nodes in the memoization map after recursing on neighbors instead of immediately after allocation: any undirected edge u <-> v or cycle causes infinite recursion unless copies[cur] = copy is written before traversing cur.neighbors.
- Validating trees using len(edges) == n - 1 alone without checking connectivity, or neglecting parent tracking in undirected cycle detection: a disconnected graph with n - 1 edges necessarily hides a cycle in one component, and traversing v -> u immediately after u -> v falsely appears as a 2-cycle unless parent is excluded.
from collections import deque
def bfs_shortest(adj, start, target):
dist, queue = {start: 0}, deque([start])
while queue:
u = queue.popleft()
if u == target:
return dist[u]
for v in adj[u]:
if v not in dist:
dist[v] = dist[u] + 1
queue.append(v)
return -1import heapq
def dijkstra(adj, start):
dist, heap = {}, [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if u in dist:
continue
dist[u] = d
for v, w in adj[u]:
if v not in dist:
heapq.heappush(heap, (d + w, v))
return distfrom collections import deque
def zero_one_bfs(adj, start):
dist, dq = {start: 0}, deque([start])
while dq:
u = dq.popleft()
for v, w in adj[u]:
if dist[u] + w < dist.get(v, float("inf")):
dist[v] = dist[u] + w
dq.appendleft(v) if w == 0 else dq.append(v)
return distdef dfs_traverse(adj, n):
seen = set()
def dfs(u):
seen.add(u)
for v in adj[u]:
if v not in seen:
dfs(v)
dfs(0)
return len(seen) == n