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

01. Network Delay Time

Optimal Target: O(E log V) time · O(V + E) space

You are given a network of n nodes labeled from 1 to n and a list of directed weighted edges times, where times[i] = [u, v, w] indicates that a signal takes w >= 0 time units to travel from source node u to target node v. Given a starting node k, return the minimum time it takes for all n nodes to receive the signal, or -1 if at least one node can never receive the signal.

EXAMPLE 1
Input: times = [[1, 2, 2], [1, 3, 5], [2, 3, 1], [2, 4, 4], [3, 4, 1], [4, 5, 3]], n = 5, k = 1
Output: 7
Explanation: Nodes 1..5 settle at shortest arrival times 0, 2, 3 (via 1 -> 2 -> 3), 4 (via 1 -> 2 -> 3 -> 4), and 7 (via 4 -> 5). Every node has received the signal once the slowest node (node 5) arrives at time 7.
EXAMPLE 2
Input: times = [[1, 2, 1]], n = 3, k = 1
Output: -1
Explanation: Node 3 has no incoming path from node 1, so len(dist) == 2 < 3 and the signal never reaches the full network.
ARCHITECTURE / DATA FLOW DIAGRAM
0122334475
AUTOMATED TEST SUITE
Test Case 1
Input: [[1, 2, 2], [1, 3, 5], [2, 3, 1], [2, 4, 4], [3, 4, 1], [4, 5, 3]], 5, 1
Expected: 7
Test Case 2
Input: [[1, 2, 1]], 3, 1
Expected: -1
Test Case 3
Input: [[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2
Expected: 2
Pattern Trigger Hint ("How to Spot It")

costs on links + cheapest arrival → Dijkstra

Python 3.14 Runtime Ready

Click ▶ Run Tests (or press ⌘+Enter) to execute network_delay_time against all 3 test cases in WebAssembly Python.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

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