CODING PATTERNS · LESSON 19 OF 28 · 57 MIN VIDEO · 18 PROBLEMS

Graphs

Module Progress (0 / 18 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (57 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

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.

WHEN TO USE THIS PATTERN
  • 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).
COMMON INTERVIEW PITFALLS
  • 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.
Breadth-First Search (Unweighted Shortest Path)Minimum steps from start to target when every transition has uniform cost 1 (over vertices or augmented states).
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 -1
Dijkstra's Algorithm (Non-Negative Weighted Shortest Path)Minimum cumulative edge weight from start when all edge weights w >= 0 (or maximum product probability using negated probabilities).
import 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 dist
0-1 BFS (Binary-Weight Shortest Path)Minimum cost when every edge weight w is strictly 0 or 1, replacing O(E log V) heap operations with O(1) deque pushes.
from 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 dist
Depth-First Search (Component & Cycle-Safe Traversal)Exploring connected components, flood-filling grids, or traversing cyclic graphs in O(V + E) time.
def 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
🔒 PRO PROBLEMTarget: O(S) S = stops over all routes

05. Bus Routes

Pattern Trigger: count switches → make each group a node

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

We want the fewest steps from S to E. Which walk guarantees it?