Phase 4 — Graph Mastery

Target level: Medium → Hard Expected duration: 3 weeks (12-week track) / 3 weeks (6-month track) / 4 weeks (12-month track) Weekly cadence: ~7 algorithms per week + 40–70 problems applying them under the framework

Why Graphs Are The Most-Tested Algorithm Family In Senior Interviews

Phase 2 taught you 28 patterns that solve most Mediums. Phase 3 taught you the augmented data structures that make Hards tractable. Phase 4 teaches the single algorithmic family that shows up more often than any other in senior, staff, and infrastructure interviews: graphs.

Here is the empirical claim, and it is the entire reason this phase exists as its own three-to-four-week unit:

Roughly one in three of all Medium-Hard and Hard interview problems at top-tier companies is a graph problem in disguise. Of those, at least half are not labeled “graph” — they are labeled “string”, “scheduler”, “permission system”, “currency conversion”, “build pipeline”, or “bus route”. The first job is recognizing that the problem is a graph problem. The second is picking the right algorithm. The third is implementing it without bugs.

Why graphs dominate senior interviews specifically:

1. Graphs are the universal modeling language. Almost every relational or topological structure in a real production system — service dependencies, ACL inheritance, package builds, request routing, social networks, fraud rings, knowledge bases, scheduling DAGs, currency markets — is a graph. A senior engineer is expected to see the graph in a problem that doesn’t mention one.
2. Graphs combine almost every Phase 1–3 building block. A real graph problem will fold in a hash map (adjacency list), a queue (BFS), a stack (DFS), a heap (Dijkstra), a DSU (Kruskal / cycle detection), a topological sort (dependency resolution), and sometimes a segment tree (Euler tour + RMQ for LCA). The interviewer gets to test ten primitives in a single 35-minute round.
3. Graphs have a clean correctness story. Each algorithm here is a named result with a known proof, known preconditions, and a known complexity. There is no “I think this works because…” — there is “this is BFS, BFS gives shortest paths in unweighted graphs, the precondition is unit-weight edges, the proof is on layer numbers.” Senior interviewers want to hear that proof come out unprompted.
4. The graph algorithm space is large but finite. Roughly 20 algorithms cover everything you’ll see at L4–L6. Past that, max-flow, min-cost-max-flow, and matching variants cover staff-and-above. There is a definite ceiling — but it’s higher than candidates expect, and it’s where senior interviewers live.

Candidates who stall on graph rounds almost always fail at recognition or modeling, not at the algorithm itself. They fail because:

• They didn’t recognize “alien dictionary” as a topological sort over inferred constraints.
• They didn’t see “minimum cost to connect all points” as Kruskal/Prim on the complete metric graph.
• They reached for Dijkstra on a graph with negative weights and produced wrong answers.
• They tried BFS on a 0-1 weighted graph instead of 0-1 BFS or Dijkstra.
• They forgot to coordinate-compress an implicit graph and exploded the state space.

This phase is structured to make those failures impossible. You will internalize the signal for each of 21 algorithms, the modeling reflex for implicit graphs, and the algorithm-selection decision tree that maps a problem statement to a single correct technique within 90 seconds.

After this phase, you can solve unmistakably-Hard graph problems on first attempt: alien dictionary in 20 minutes, network delay time in 10, cheapest flights in K stops in 25, accounts merge in 20, bus routes in 30, min cost to connect all points in 15. You also become visibly stronger in mock interviews because you immediately reach for adjacency lists, write from collections import deque before you write any logic, and articulate which algorithm you’re running and why.

What You Will Be Able To Do After This Phase

• Recognize that a problem is a graph problem in <2 minutes of reading, even when neither “graph”, “node”, nor “edge” appears in the statement.
• Choose between BFS / DFS / Dijkstra / Bellman-Ford / Floyd-Warshall / 0-1 BFS / topological sort / DSU / MST in <60 seconds based on the problem’s edge weights, query type, and size.
• Implement a clean adjacency-list representation in <2 minutes for any graph variant (directed, undirected, weighted, multi-edge, self-loop, implicit grid).
• Implement BFS, DFS (recursive + iterative), Dijkstra (eager and lazy), and topological sort (Kahn + DFS) from memory in <8 minutes each.
• Detect cycles in directed and undirected graphs by both DFS-coloring and DSU.
• Run Kruskal and Prim end-to-end with a DSU you write by hand.
• Identify when a Hard problem reduces to bipartite matching or max-flow at the modeling level (you do not need to memorize Dinic).
• Articulate the correctness theorem for every algorithm you use (“Dijkstra is correct because the heap always extracts the next-closest unsettled node, and that node’s tentative distance is its true shortest distance under non-negative weights”).
• Recognize negative-cycle problems and reach for Bellman-Ford / SPFA correctly.
• Construct the implicit graph for grid problems, word ladders, state-space search, and bus-route problems without ever materializing all edges.

How To Read This Phase

Read this README in two passes. Pass 1: linear, end to end, building a mental map of which algorithm plugs which signal. Pass 2: as you work the labs, refer back to specific algorithm entries to clarify invariants and pitfalls.

Each algorithm entry has a fixed shape:

1. When To Use — the problem signal that should fire this algorithm in <2 minutes.
2. Complexity — time and space, with the assumptions that matter.
3. Correctness Sketch — one paragraph that you should be able to recite under interviewer pressure.
4. Common Pitfalls — the bugs that consume the most interview minutes.
5. Classic Problems — 3–6 representative LeetCode problems where the algorithm is the intended solution.

The phase ends with a Graph-Modeling Cheat Sheet (how to recognize a graph problem in disguise), an Implicit-Graph Catalog (grid / word-ladder / state-space), a Mastery Checklist, and Exit Criteria.

Inline Graph Algorithm Reference

1. Graph Representation

When To Use

Every graph problem starts here. The choice between adjacency list, adjacency matrix, edge list, and implicit graph is the first decision you make, and it shapes every subsequent algorithm’s complexity.

• Adjacency list — the default. adj[u] is a list of (neighbor, weight) pairs. Use a dict of list (Python), Map<Integer, List<int[]>> (Java), [][]int or map[int][]edge (Go), vector<vector<pair<int,int>>> (C++).
• Adjacency matrix — M[u][v] is the edge weight (or 0 / ∞ for absence). Use only when (a) V ≤ 500 so the O(V²) memory fits, (b) you do many (u, v) edge-existence queries, or (c) you’re running Floyd-Warshall.
• Edge list — a flat list of (u, v, w) triples. Use only when the algorithm is edge-centric: Kruskal, Bellman-Ford.
• Implicit graph — never materialize the edges. The neighbors of a state are computed on demand. Used for grids, word ladders, sliding puzzles, state-space search.

Complexity

Correctness Sketch

The representation is a faithful encoding of the graph; the algorithm’s correctness is independent of representation as long as iteration over neighbors is exhaustive and edge weights are preserved. Use the representation that minimizes the algorithm’s dominant cost.

Common Pitfalls

• Undirected edges added once instead of twice. adj[u].append(v) without adj[v].append(u) silently breaks every traversal that relies on bidirectionality.
• Multi-edges silently lost when using a set instead of a list for neighbors. If the problem permits multi-edges, use lists; if not, decide explicitly.
• Self-loops can appear in problems that don’t seem to allow them (e.g., topological sorts of “course depends on itself”). Handle defensively.
• Indexing on string keys — convert string node IDs to ints once, up front. Hash lookups inside hot loops cost real time.

Classic Problems

• LeetCode 261 — Graph Valid Tree (tests representation + cycle detection).
• LeetCode 332 — Reconstruct Itinerary (multi-edges matter; use a heap-of-destinations).
• LeetCode 547 — Number of Provinces (matrix vs list tradeoff).

2. BFS — Breadth-First Search (Unweighted Shortest Path)

When To Use

• Find shortest path in number of edges in an unweighted (or unit-weight) graph.
• Layer-by-layer traversal: “all nodes at distance ≤ k”, “minimum number of moves”, “level-order traversal”.
• The problem says “minimum / shortest / fewest” and the edge weights are all equal.
• Implicit graph variants: shortest word ladder, shortest path in a maze, fewest knight moves on a chessboard.

Complexity

Time O(V + E). Space O(V) for the queue and visited set.

Correctness Sketch

BFS visits nodes in non-decreasing order of distance from the source. When a node is first dequeued, its distance is exactly the shortest path length, because any earlier-enqueued node has distance ≤ the current node’s distance, and the current node was enqueued by a neighbor at distance d - 1 — so any other path to it must go through some node at distance ≥ d - 1, giving total distance ≥ d.

Common Pitfalls

• Marking visited on dequeue, not on enqueue. If you mark on dequeue, the same node can be enqueued by every neighbor before it’s processed once — exploding the queue to O(E) size and degrading performance.
• Tracking distance via len(queue) confusion. Use either a (node, dist) tuple or process the queue in level batches via for _ in range(len(queue)).
• Not separating the visited check from the enqueue. if v not in visited: visited.add(v); queue.append(v) is the canonical idiom.
• Forgetting to handle the source itself. The source’s distance is 0; it should be marked visited at start.

Classic Problems

• LeetCode 102 — Binary Tree Level Order Traversal.
• LeetCode 127 — Word Ladder (canonical BFS on implicit graph). See Lab 01.
• LeetCode 200 — Number of Islands (BFS variant on grid).
• LeetCode 433 — Minimum Genetic Mutation.
• LeetCode 1091 — Shortest Path in Binary Matrix.

3. DFS — Depth-First Search (Recursive + Iterative; Pre/Post Numbering)

When To Use

• Connected-component enumeration, cycle detection, topological sort, tree traversal, articulation-point detection.
• Backtracking-style problems where you exhaustively explore a state space.
• When path matters more than distance — DFS finds some path, not necessarily the shortest.
• When the graph has small branching but deep paths.

Complexity

Time O(V + E). Space O(V) for the recursion stack (or explicit stack).

Correctness Sketch

DFS explores each edge exactly twice (once in each direction for undirected, once for directed). Pre-order numbering captures discovery time; post-order captures finish time. The discovery/finish interval structure underpins SCC, articulation-point, and bridge algorithms (Tarjan’s lowlink uses pre-order numbers as ranks).

Common Pitfalls

• Stack overflow at V = 10^5 in Python. Default recursion limit is 1000. Either sys.setrecursionlimit(2 * 10**5) or convert to an explicit stack.
• Iterative DFS state. When converting to a stack, you need to track where in the neighbor iteration you are — a tuple of (node, iterator) works; a tuple of (node, neighbor_index) is faster.
• Pre vs post processing confusion. “Print on entry” is pre-order; “print on completion” is post-order; topological sort uses reverse post-order.
• Visited semantics differ from BFS. For cycle detection in directed graphs, you need three states: white (unvisited), gray (on the current DFS path), black (fully explored). A single boolean visited is insufficient.

Classic Problems

• LeetCode 200 — Number of Islands. See Lab 02.
• LeetCode 695 — Max Area of Island.
• LeetCode 207 — Course Schedule (cycle detection via DFS coloring).
• LeetCode 332 — Reconstruct Itinerary (Hierholzer’s = post-order DFS).
• LeetCode 332 — Surrounded Regions.

4. Multi-Source BFS

When To Use

• “From any of these K starting points, what’s the shortest distance to every other node?” — common in grids.
• Equivalent to adding a virtual super-source connected to all K starts with weight 0 and running single-source BFS. But you don’t materialize the super-source: you just enqueue all K starts at distance 0 simultaneously.
• Examples: “rotting oranges” (every rotten orange is a source), “walls and gates” (every gate is a source), “01 matrix distance from nearest zero” (every zero is a source).

Complexity

Time O(V + E). Same as single-source BFS — the K starts add O(K) but are absorbed into the V + E term.

Correctness Sketch

The super-source argument: imagine a node S₀ connected to every start with weight 0. Single-source BFS from S₀ visits each real node in non-decreasing distance order, and the distance is 1 + min(dist(start_i)). By initializing the queue with all starts at distance 0 instead of materializing S₀, we get the same layer-by-layer behavior with the same correctness proof.

Common Pitfalls

• Initializing one start at a time in a loop and running single-source BFS K times. That’s O(K · (V + E)), not O(V + E).
• Forgetting to mark all starts visited up front. If you only mark the first as visited, the others are treated as unvisited targets and get re-enqueued at distance > 0.
• Mixing source types in problems where some sources and some targets are both special (e.g., “rotting oranges” has rotten=source, fresh=target, empty=skip). Always classify cells in a single pass before BFS.

Classic Problems

• LeetCode 994 — Rotting Oranges. See Lab 03.
• LeetCode 286 — Walls and Gates.
• LeetCode 542 — 01 Matrix.
• LeetCode 1162 — As Far From Land As Possible.
• LeetCode 815 — Bus Routes (multi-source on the bus-line graph). See Lab 09.

5. 0-1 BFS

When To Use

• Edge weights are in {0, 1} (or any two values, with 0-weight as the “free” edge).
• The graph mixes “free” transitions (0-weight) and “step” transitions (1-weight). Examples: grid with portals, terrain with roads (free) and trails (cost 1).
• Dijkstra would also work but has a log V overhead. 0-1 BFS is O(V + E) — strictly faster.

Complexity

Time O(V + E). Space O(V).

Correctness Sketch

Use a deque. When relaxing an edge of weight 0, push the neighbor to the front; when relaxing weight 1, push to the back. The deque thus holds nodes in non-decreasing order of tentative distance, with at most two distinct distance values present at any moment. The first time a node is popped, its distance is final — same correctness argument as Dijkstra, with the deque playing the role of a 2-bucket priority queue.

Common Pitfalls

• Pushing weight-1 edges to the front is the canonical bug — it breaks the monotone-distance invariant.
• Re-processing nodes because you didn’t check if d > dist[u]: continue after popping. This is a Dijkstra-style guard.
• Generalizing to weights {0, k} for k > 1 doesn’t work directly; you need either a multi-bucket BFS or actual Dijkstra.

Classic Problems

• LeetCode 1368 — Minimum Cost to Make at Least One Valid Path in a Grid (canonical 0-1 BFS).
• LeetCode 2290 — Minimum Obstacle Removal to Reach Corner.
• “Shortest path with at most K edges of cost 1, others free” — folklore.

6. Dijkstra (Lazy + Eager Variants; Non-Negative Weights)

When To Use

• Single-source shortest path in a graph with non-negative edge weights.
• The default for any “shortest / cheapest / minimum cost” path problem with weighted edges. If weights can be negative, use Bellman-Ford instead.
• Variants: “shortest path with at most K edges” (relax with a (dist, edges_used) state), “second shortest path” (two distance arrays), “shortest path on multi-criteria” (state expansion).

Complexity

• Lazy (binary heap): O((V + E) log V). The heap holds up to E entries because we don’t decrease-key — we re-insert and skip stale entries on pop.
• Eager (binary heap with decrease-key): O((V + E) log V) — same asymptotic, smaller constant, but decrease-key requires an indexed heap.
• Fibonacci heap: O(E + V log V) — theoretical, never used in interviews.
• Space O(V) for the dist array + O(E) for the heap (lazy).

Correctness Sketch

Maintain a tentative distance dist[v] for every node, initialized to ∞ except the source (0). Repeatedly extract the unsettled node u with smallest dist[u] (the heap gives this in O(log V)). At the moment of extraction, dist[u] is final: any other path to u must go through some other unsettled node w with dist[w] ≥ dist[u], and since edges are non-negative, the total path length to u via w is ≥ dist[u]. Relax all outgoing edges from u and push updated neighbors. Termination: every node is extracted at most once.

Common Pitfalls

• Using Dijkstra on negative-weight edges. It produces wrong answers — the relaxation invariant fails. Use Bellman-Ford.
• Lazy variant: forgetting the staleness check. if d > dist[u]: continue after popping. Without it, you re-process nodes and the asymptotic blows up to O(E²).
• Pushing (dist[u], u) instead of (new_dist, neighbor) when relaxing — the heap orders on the first tuple element, so put dist first.
• Initializing dist[source] = 0 but not pushing the source to the heap. The first pop must be the source.
• Forgetting to handle disconnected components. dist[v] = ∞ is the answer for unreachable v; check before printing.

Classic Problems

• LeetCode 743 — Network Delay Time. See Lab 04.
• LeetCode 1631 — Path With Minimum Effort.
• LeetCode 778 — Swim in Rising Water.
• LeetCode 787 — Cheapest Flights Within K Stops (modified Dijkstra with edge-budget).
• LeetCode 1514 — Path with Maximum Probability (Dijkstra on max-multiplicative).

7. Bellman-Ford (Negative Weights, Negative-Cycle Detection)

When To Use

• Shortest path with negative edge weights but no negative cycle reachable from source.
• Negative-cycle detection itself: if a V-th iteration relaxes any edge, the graph has a negative cycle on the source’s reachable component.
• “Shortest path with at most K edges” — Bellman-Ford’s iteration index is the edge budget. This is the canonical reframing of LeetCode 787.
• All-pairs negative shortest paths via Johnson’s algorithm (Bellman-Ford + Dijkstra), but this is overview-only.

Complexity

Time O(V · E). Space O(V).

Correctness Sketch

After i rounds of relaxing all E edges, dist[v] equals the shortest path from source to v using at most i edges. By induction: in round 1, only the source’s neighbors are relaxed (1-edge paths). In round i, any shortest i-edge path’s last edge (u, v) was relaxed because dist[u] was already correct for i - 1 edges. Since shortest paths in a graph with no negative cycle have ≤ V - 1 edges, V - 1 rounds suffice. A V-th round that still relaxes an edge proves a negative cycle.

Common Pitfalls

• Iterating until no edge is relaxed (early termination) is a common variant — but you still need V - 1 rounds in the worst case for correctness, and the V-th round for cycle detection.
• Using a dict for distances instead of an array indexed by int — slow on hot iteration loops.
• Confusing “shortest path with at most K edges” with “K hops” — read the problem carefully. K stops in LC 787 is K + 1 edges.
• Negative-cycle reachability. A negative cycle exists in the graph but doesn’t affect the source if it’s unreachable. Run from the source, not globally.

Classic Problems

• LeetCode 787 — Cheapest Flights Within K Stops (canonical). See Lab 05.
• “Detect arbitrage in currency markets” (negative cycle in -log(rate) graph).
• “Minimum steps to make k operations” with negative-cost shortcuts.

8. SPFA (Shortest Path Faster Algorithm)

When To Use

• Bellman-Ford with a queue-based optimization that avoids re-relaxing edges whose source u hasn’t been updated since the last visit.
• In practice, ~2–10× faster than vanilla Bellman-Ford on sparse graphs with random structure.
• Caveat: worst-case is still O(V · E). On adversarial inputs (e.g., gridded negative cycles), SPFA can be slower than Bellman-Ford. Codeforces problems are sometimes designed to break SPFA. Use it for negative-weight graphs in interviews only when you’ve stated the caveat.

Complexity

Average O(k · E) for small k (often k ≤ 2). Worst-case O(V · E). Space O(V) for the queue + an in_queue flag.

Correctness Sketch

A node u is enqueued whenever its dist[u] improves. On dequeue, relax all outgoing edges. The in_queue flag prevents duplicate enqueues. Termination follows from the fact that each dist[u] decreases monotonically and is bounded below — for a graph with no negative cycle, the total number of decreases is ≤ V · E.

Common Pitfalls

• Forgetting the in_queue flag. Without it, the queue can grow to O(E) size and SPFA degrades.
• Negative-cycle detection in SPFA requires tracking the number of times each node is relaxed; if a node is relaxed ≥ V times, there’s a negative cycle.
• Adversarial inputs. State the caveat to the interviewer; don’t claim asymptotic improvement.

Classic Problems

• Same as Bellman-Ford. Choose Bellman-Ford for the K-edge-budget framing (LC 787); SPFA only when raw single-source negative shortest path is the goal and average performance matters.

9. Floyd-Warshall (All-Pairs Shortest Paths)

When To Use

• All-pairs shortest paths on a small graph: V ≤ ~500 (V³ = 10^8, ~1 second).
• Negative weights are fine (no negative cycle assumed).
• Transitive closure: replace min/+ with OR/AND to compute reachability in O(V³).
• Density independence: the algorithm is V³ regardless of E. So on dense graphs (E ~ V²) it’s the only practical all-pairs algorithm; on sparse graphs (E ~ V) Dijkstra-from-each-node is V · E · log V = better when V is large.

Complexity

Time O(V³). Space O(V²) for the distance matrix.

Correctness Sketch

Define dp[k][i][j] = shortest path from i to j using only intermediate vertices in {1, ..., k}. The recurrence is dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j]) — either don’t use k, or use it as a midpoint. The 2D in-place version dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) works because in iteration k, the row dist[i][k] and column dist[k][j] are updated only with paths that don’t use k as an intermediate (since k-as-intermediate requires using k twice, which is a cycle and dominated by no-use).

Common Pitfalls

• Loop order is k, then i, then j — and not i, j, k. The latter computes garbage.
• Negative-cycle detection is dist[i][i] < 0 after the algorithm completes.
• Initializing diagonals — dist[i][i] = 0; missing edges are ∞ (use a large finite number like 10^9 to avoid overflow when summing).
• Path reconstruction requires a parent matrix — easy to add but double the memory.

Classic Problems

• LeetCode 1334 — Find the City With the Smallest Number of Neighbors at a Threshold Distance (canonical V ≤ 100 Floyd-Warshall).
• LeetCode 743 — Network Delay Time (single-source, but Floyd-Warshall on V ≤ 100 still passes).
• “Transitive closure of a DAG” via OR/AND Floyd-Warshall.

10. Topological Sort (Kahn + DFS-Based; Cycle-Detection Equivalence)

When To Use

• DAG ordering where edge u → v means “u must come before v”.
• “Course schedule”, “task dependencies”, “build order”, “alien dictionary” (after extracting constraint edges).
• Used as a precondition check: if topological sort fails (cycle present), the problem has no valid ordering.

Complexity

Time O(V + E). Space O(V).

Correctness Sketch — Kahn’s

Repeatedly remove a node with in-degree 0, append it to the order, and decrement its neighbors’ in-degrees. If the order has length V at the end, the graph is a DAG and the order is valid. If not, the remaining nodes form a cycle. Correctness: a node with in-degree 0 has no predecessors, so it can safely come first. After removal, the remaining graph is still a DAG (removing vertices can’t create cycles).

Correctness Sketch — DFS-Based

Run DFS from each unvisited node; on finishing a node (post-order), prepend it to the result. This works because of the white-path lemma: if u → v and DFS visits u before v, then v is in u’s subtree, so v finishes before u, so v is appended before u and prepended after u — meaning u comes before v in the final order.

Common Pitfalls

• Edge direction confusion. “X depends on Y” usually means edge Y → X (Y must come first). Read the problem carefully.
• Detecting cycles via Kahn’s — count nodes processed; if < V, cycle exists.
• Multiple valid orders — both Kahn’s and DFS-based produce some valid order, not a unique one. If the problem demands lexicographically smallest, use Kahn’s with a min-heap instead of a queue.

Classic Problems

• LeetCode 207 — Course Schedule.
• LeetCode 210 — Course Schedule II.
• LeetCode 269 — Alien Dictionary. See Lab 06.
• LeetCode 1136 — Parallel Courses.
• LeetCode 2115 — Find All Possible Recipes from Given Supplies.

11. Cycle Detection In Directed Graphs (DFS Color States)

When To Use

• “Does this directed graph have a cycle?” — in dependency / scheduling / DAG-validation problems.
• More fine-grained than Kahn’s: tells you which edge closes a cycle.

Complexity

Time O(V + E). Space O(V) for the color array.

Correctness Sketch

Maintain three colors: white (unvisited), gray (on the current DFS path), black (fully explored). On entering a node, mark it gray; on finishing, mark it black. If during DFS we encounter a gray neighbor, that’s a back-edge and proves a cycle. White → recurse. Black → already processed; not part of current path; safe to ignore. Correctness: a back-edge is exactly an edge from a descendant to an ancestor in the DFS tree, which closes a cycle. Forward and cross edges don’t.

Common Pitfalls

• Using a single boolean visited. A visited node could be a back-edge target (cycle) or a forward/cross-edge target (no cycle). Two-state visited can’t distinguish. Three colors are required.
• Resetting gray to white on finish. Wrong — you’d keep re-marking black nodes as gray on subsequent DFS calls and produce phantom cycles. Mark black on finish and stay black.
• Forgetting to check both directions in undirected graphs. This algorithm is for directed graphs; for undirected, see #12.

Classic Problems

• LeetCode 207 — Course Schedule (DFS-color variant).
• LeetCode 802 — Find Eventual Safe States (reverse-direction + cycle-detection).
• LeetCode 1059 — All Paths from Source Lead to Destination.

12. Cycle Detection In Undirected Graphs (DFS / Union-Find)

When To Use

• “Is this undirected graph a tree (acyclic + connected)?”, “redundant edge”, “valid tree”.
• Two equivalent approaches: DFS with parent tracking, or DSU.

Complexity

DFS: O(V + E). DSU: O(E · α(V)).

Correctness Sketch — DFS

In an undirected graph, every edge is bidirectional in the adjacency list. When DFS visits v from u, the edge (v, u) shows up in v’s adjacency. Skip the parent: for w in adj[v]: if w != parent: dfs(w, v). If a non-parent neighbor is already visited, that’s a cycle-closing edge.

Correctness Sketch — DSU

Process edges in any order. For each edge (u, v): if find(u) == find(v), the edge would close a cycle (both endpoints already in same component); else union(u, v). After processing all edges, the graph is acyclic iff no cycle was reported.

Common Pitfalls

• DFS: forgetting to skip the parent. Without if w != parent, every edge looks like a back-edge.
• DFS: parallel edges — if the graph has multi-edges between u and v, the second edge looks like a back-edge through a non-parent neighbor. Track edge IDs, not just parent node.
• DSU: ignoring connectedness. “Valid tree” requires both acyclic and connected (V - 1 edges + DSU returning a single component).

Classic Problems

• LeetCode 261 — Graph Valid Tree.
• LeetCode 684 — Redundant Connection (DSU canonical).
• LeetCode 685 — Redundant Connection II (directed variant — harder).

13. Strongly Connected Components (Kosaraju + Tarjan)

When To Use

• Decompose a directed graph into maximal sets where every pair (u, v) has paths in both directions.
• Reduces a directed graph to a DAG of SCCs (the condensation).
• Used in 2-SAT, transitive-closure compression, and “find all nodes that can reach all others”.

Complexity

Both Kosaraju and Tarjan: O(V + E). Space O(V).

Correctness Sketch — Kosaraju

1. DFS on the original graph, pushing nodes to a stack in post-order.
2. Build the reverse graph.
3. Pop nodes from the stack; for each unvisited node, DFS on the reverse graph — that DFS visits exactly one SCC.

The post-order ordering ensures the first node popped is in a “source” SCC of the condensation; reverse-DFS from it can only reach nodes in its own SCC because no other SCC’s nodes have a forward path back to it.

Correctness Sketch — Tarjan

Single DFS maintaining a stack of “currently active” nodes plus disc[u] (discovery time) and low[u] (lowest discovery time reachable via the subtree + at most one back-edge). When DFS finishes a node u and low[u] == disc[u], pop the stack down to and including u — those popped nodes form an SCC. Tarjan does it in one pass; Kosaraju in two passes but with simpler bookkeeping.

Common Pitfalls

• Kosaraju: forgetting to reverse all edges in the second graph. Use a separate adjacency list.
• Tarjan: confusing low with disc — low[u] = min(low[u], low[v]) for tree-edge children; low[u] = min(low[u], disc[v]) for back-edge neighbors that are still on the stack. Both updates are needed.
• Tarjan: handling cross-edges to other SCCs. A neighbor that’s been finished is already in a different SCC; do not update low[u] from it.

Classic Problems

• LeetCode 1192 — Critical Connections (Tarjan for bridges; SCC-adjacent).
• “2-SAT solvability” via SCCs in the implication graph.
• “Number of source SCCs in the condensation” — Codeforces classic.

14. Bridges And Articulation Points (Tarjan’s Lowlink)

When To Use

• A bridge is an edge whose removal disconnects the graph.
• An articulation point is a vertex whose removal disconnects the graph.
• Used in “critical connections” problems and network-resilience analysis.

Complexity

O(V + E). Single DFS, one pass.

Correctness Sketch

Compute disc[u] and low[u] as in Tarjan’s SCC. For an edge (u, v) where v is a tree child: low[v] > disc[u] ⇒ (u, v) is a bridge (no back-edge from v’s subtree reaches anything at-or-above u, so removing (u, v) disconnects). For articulation points: u is an articulation point if (a) u is the DFS root and has ≥ 2 tree children, or (b) u is not the root and has a tree child v with low[v] ≥ disc[u].

Common Pitfalls

• Using ≥ vs > — bridges use low[v] > disc[u]; articulation points use low[v] ≥ disc[u]. The off-by-one between them is critical.
• DFS root special case for articulation points — must count tree children; with one tree child, removing the root doesn’t disconnect.
• Multi-edges — a multi-edge between u and v is not a bridge (the parallel edge keeps the graph connected). Treat parallel edges by edge-ID, not endpoint pair.

Classic Problems

• LeetCode 1192 — Critical Connections in a Network (canonical bridges).
• “Find all articulation points in a network” — Codeforces classic.

15. Minimum Spanning Tree — Kruskal (With DSU)

When To Use

• Connect all V nodes with the minimum total edge weight, in a graph with V - 1 chosen edges.
• Edge-centric algorithm: sort edges, add greedily, skip those that close a cycle (DSU detects).
• Best on sparse graphs (E ~ V) where sorting E edges dominates.

Complexity

O(E log E) for sort + O(E · α(V)) for DSU = O(E log E). Space O(V).

Correctness Sketch (Cut Property)

The minimum-weight edge crossing any cut of the graph belongs to some MST. Kruskal repeatedly takes the next-cheapest edge; if it doesn’t close a cycle (DSU find(u) != find(v)), it’s the cheapest edge crossing the cut between its DSU components. By the cut property, it’s in some MST. Adding it preserves the invariant that the chosen edges are a subset of some MST. After V - 1 edges, the chosen set is a spanning tree.

Common Pitfalls

• Forgetting to sort edges. Kruskal without sorting is just a random spanning tree.
• DSU bugs. Phase 3’s α(N) DSU is required. Recursive find blows the stack at V = 10^5; use iterative two-pass or path-halving.
• Disconnected graph. If after processing all edges DSU has > 1 component, no spanning tree exists. Return failure or compute a minimum spanning forest.
• Tie-breaking on equal weights — any tie-breaking rule works; they all produce some MST.

Classic Problems

• LeetCode 1584 — Min Cost to Connect All Points. See Lab 08.
• LeetCode 1135 — Connecting Cities With Minimum Cost.
• LeetCode 1489 — Find Critical and Pseudo-Critical Edges in MST.

16. Minimum Spanning Tree — Prim (With Priority Queue)

When To Use

• Same problem as Kruskal — minimum total edge weight to connect all V.
• Vertex-centric algorithm: grow the tree one vertex at a time, always adding the minimum-weight edge from the tree to a non-tree vertex.
• Best on dense graphs where the heap pays off relative to sorting all E edges.

Complexity

With binary heap: O((V + E) log V). With Fibonacci heap: O(E + V log V) (theoretical). Space O(V + E).

Correctness Sketch (Cut Property, Variant)

At every step, the partial tree T defines a cut (T vs not-T). The minimum-weight edge crossing this cut is added next. By the cut property, it belongs to some MST. The invariant — chosen edges ⊆ some MST — is preserved. After V - 1 additions, the tree spans all of V.

Common Pitfalls

• Lazy vs eager Prim. Lazy: push every (weight, neighbor) to the heap, skip duplicates on pop. Eager: maintain a “best known weight to enter T” per non-tree vertex and use decrease-key. Lazy is simpler and asymptotically equivalent.
• Disconnected graph — same as Kruskal; the heap empties before V - 1 edges are added.
• Picking starting vertex — any vertex works for connected graphs.

Classic Problems

• LeetCode 1584 — Min Cost to Connect All Points (also solvable via Prim).
• “Maximum spanning tree” via negated weights.

17. Bipartite Check (BFS/DFS 2-Coloring)

When To Use

• “Can we partition the V into two groups such that every edge crosses groups?”
• Equivalent to: graph has no odd cycle.
• Used as a precondition for bipartite matching, and in problems like “is this set of dislike-pairs separable into two camps?”

Complexity

O(V + E). Space O(V).

Correctness Sketch

BFS/DFS, coloring each visited node alternately (color 0 or 1) from its parent. If we ever try to color a visited node with a color different from its existing color, the graph has an odd cycle and is not bipartite. Correctness: BFS layers alternate colors; an edge within a layer (or skipping ≥ 2 layers) violates bipartiteness; specifically, any odd cycle forces a same-layer edge.

Common Pitfalls

• Disconnected graph. Run BFS from every unvisited node; the bipartiteness of each component is independent.
• Initializing colors as -1 (uncolored), 0, 1. A boolean visited is insufficient; you need the actual color.
• Counting color-0 vs color-1 sizes when the problem asks for “minimum group size” — but the partitioning is unique only up to swapping the two colors per connected component.

Classic Problems

• LeetCode 785 — Is Graph Bipartite?
• LeetCode 886 — Possible Bipartition.
• “2-coloring as a sanity check before bipartite matching.”

18. Bipartite Matching (Hungarian / Hopcroft-Karp Overview)

When To Use

• Maximum cardinality matching in a bipartite graph: pair up as many left-side nodes with right-side nodes as possible, using each at most once.
• Job assignment, “find as many distinct words to slots as possible”, “schedule maximum tasks to workers”.
• Hungarian algorithm: O(V · E) via repeated augmenting-path BFS — ~O(V²·√V) on bipartite.
• Hopcroft-Karp: O(E · √V) — strictly better; the algorithm of choice for large bipartite matching.

Complexity

Hungarian: O(V · E). Hopcroft-Karp: O(E · √V). Space O(V + E).

Correctness Sketch (König’s Theorem and Augmenting Paths)

Berge’s theorem: a matching M is maximum iff there is no augmenting path (a path alternating unmatched / matched edges, starting and ending at unmatched vertices). The Hungarian algorithm repeatedly finds augmenting paths via BFS/DFS and augments. Hopcroft-Karp accelerates by finding all shortest augmenting paths in a single BFS phase, then augmenting all of them in one DFS phase.

Common Pitfalls

• Confusing maximum matching with maximum-weight matching. The latter is min-cost-max-flow; harder algorithm.
• Implementing matching from scratch in interviews is rare. State the algorithm by name, reduce to it, and note the complexity. Senior interviewers accept “this is bipartite matching, O(E√V) via Hopcroft-Karp” without code.
• Modeling. The hard part is recognizing the bipartite structure. “Are there two disjoint sets where edges only cross sets?”

Classic Problems

• LeetCode 1947 — Maximum Compatibility Score Sum (small N: bitmask DP. Large N: bipartite matching + weights).
• “Maximum number of distinct words to slots” — folklore.
• LeetCode 1349 — Maximum Students Taking Exam (bipartite + bitmask).

Overview-level only. Implementation drills are Phase 7 / 12.

19. Max Flow (Ford-Fulkerson / Edmonds-Karp / Dinic — Overview + When To Use)

When To Use

• “Maximum amount of flow from source S to sink T in a capacitated network.”
• Reductions: bipartite matching → max flow. Edge-disjoint paths → max flow. Min cut → max flow.
• Algorithms:
  • Ford-Fulkerson (DFS-based augmenting): O(E · max-flow) — pseudo-polynomial; can loop forever on irrational capacities.
  • Edmonds-Karp (BFS-based augmenting): O(V · E²). Polynomial.
  • Dinic’s: O(V² · E) — uses BFS levels + DFS-blocking-flow. Practical for V, E up to 10^4–10^5.

Complexity

See above. Space O(V + E) for the residual graph.

Correctness Sketch (Max-Flow Min-Cut Theorem)

The maximum flow equals the minimum cut capacity. An augmenting path in the residual graph proves the current flow is not maximum; absence of any augmenting path proves it is. Dinic’s enhancement: BFS to compute layered graph, DFS to push blocking flow, repeat until no augmenting path. Each phase strictly increases the BFS distance from S to T, bounded by V phases.

Common Pitfalls

• Implementation in 35-minute interviews is rare. State the algorithm by name, model the problem, and let the interviewer guide depth.
• Residual graph forgetting reverse edges. Every forward edge u → v of capacity c adds a reverse edge v → u of capacity 0; pushing flow f on forward subtracts from forward residual and adds to reverse residual. Without reverse edges, augmenting paths can’t “undo” prior bad choices and the max-flow can be wrong.
• Modeling errors. “Each node has capacity” requires node-splitting (split v into v_in and v_out with edge capacity = node capacity).

Classic Problems

• “Maximum bipartite matching via max-flow.”
• “Edge-disjoint paths from S to T.”
• LeetCode-style: very rare. Common in Google L5+ system rounds and competitive programming.

Overview-level. Implementation in Phase 12.

20. Min-Cut / Max-Flow Duality (Problem Modeling)

When To Use

• “Minimum cost to disconnect S from T” → min-cut problem.
• “Minimum number of edges to remove to disconnect” → min-cut on unit-capacity edges.
• “Image segmentation as binary labeling” → min-cut on a constructed graph.
• “Project selection” (some projects depend on others; pick a subset to maximize profit) → min-cut.

Complexity

Same as max-flow (compute the cut from the residual graph after max-flow terminates).

Correctness Sketch (Max-Flow Min-Cut Theorem)

In any flow network, max-flow value = min-cut capacity. After running max-flow, the min cut consists of the edges from {nodes reachable from S in residual graph} to {nodes not reachable}. Their original capacities sum to the max-flow value.

Common Pitfalls

• Recognizing the model. This is the hardest part. “Project selection” doesn’t look like a flow problem; recognizing the bipartite encoding is the senior-level skill.
• Edge orientation. Min-cut on undirected graphs: each undirected edge becomes two directed edges, each with capacity c.

Classic Problems

• “Project Selection Problem” — folklore.
• “Image Segmentation via Min-Cut” — vision systems.
• “Minimum number of edges to disconnect” — Menger’s theorem.

21. Eulerian Path / Circuit (Hierholzer’s Algorithm)

When To Use

• “Visit every edge exactly once” — Eulerian path/circuit.
• An undirected graph has an Eulerian circuit iff every vertex has even degree (and the graph is connected on edges). It has an Eulerian path iff exactly 0 or 2 vertices have odd degree.
• A directed graph has an Eulerian circuit iff every vertex has in-degree = out-degree. It has an Eulerian path iff exactly one vertex has out-degree − in-degree = 1 (start) and one has in-degree − out-degree = 1 (end).
• Hierholzer’s algorithm finds the path/circuit in O(E).

Complexity

O(V + E).

Correctness Sketch (Hierholzer’s)

DFS from the start vertex, consuming edges as you traverse them (remove from adjacency). When stuck at a vertex with no outgoing edges, prepend it to the path. Backtrack and continue from earlier vertices that still have unused outgoing edges. The final reverse of the recorded sequence is an Eulerian path. Correctness: each edge is consumed exactly once; the post-order finishing structure naturally constructs the path in reverse.

Common Pitfalls

• Multi-edges and self-loops are common in Eulerian problems. Use a multiset or a list of edges with a “consumed” flag.
• Disconnected components on edges (vs vertices). Isolated vertices with degree 0 are fine; they don’t break Eulerian-ness.
• Lexicographically smallest Eulerian path (LC 332) — sort each adjacency list and use a multiset / heap; pop the smallest unused edge first.

Classic Problems

• LeetCode 332 — Reconstruct Itinerary (canonical Hierholzer’s).
• LeetCode 753 — Cracking the Safe (Eulerian path on de Bruijn graph).

Graph-Modeling Cheat Sheet — How To Recognize A Graph Problem In Disguise

The hardest skill in this phase is modeling: recognizing that a problem is a graph problem when nothing in the statement says “graph”. Here is a battery of signals.

Common Implicit Graphs

These are the four canonical implicit-graph patterns. You should be able to spot all four within 30 seconds of reading the problem.

1. Grid Graphs

Each cell (r, c) is a node; edges go to the 4 (or 8) neighbors that satisfy bounds and the cell-type constraint. Never materialize all V·M edges — compute neighbors on demand.

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def neighbors(r, c):
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#':
            yield (nr, nc)

Variants: 8-connected, weighted edges (cost = cell value), constraint-aware (can only enter from certain directions), gravity-based.

2. Word-Ladder Graphs

Each word is a node; an edge connects two words that differ in exactly one character. With N words of length L over alphabet σ, materializing all edges is O(N²) worst case. The trick: for each word, generate L · σ “wildcarded” patterns and use a dict-of-list to find neighbors in O(L · σ) per word.

buckets = defaultdict(list)
for w in words:
    for i in range(len(w)):
        buckets[w[:i] + '*' + w[i+1:]].append(w)
def neighbors(w):
    for i in range(len(w)):
        yield from buckets[w[:i] + '*' + w[i+1:]]

3. State-Space Search

Each “state” of the system is a node; transitions are edges. The state encodes the full configuration: e.g., a tuple of (position, keys_collected) for “shortest path with key-collection”.

def neighbors(state):
    pos, keys = state
    for next_pos in adjacent_cells(pos):
        if next_pos has key K:
            yield (next_pos, keys | (1 << K))
        else:
            yield (next_pos, keys)

4. Bipartite “Token / Container” Graphs

Two sets of nodes — e.g., users and groups, buses and stops, courses and prerequisites. An edge connects a token to a container it belongs to. Multi-source BFS over this graph gives “minimum tokens needed to traverse from container A to container B” — the canonical “bus routes” framing in LeetCode 815.

See Lab 09 for the bus-routes modeling exercise.

Mastery Checklist

Before exiting this phase, verify all of these:

• You can build an adjacency list from an edge list (directed and undirected) in <2 minutes, in your primary language.
• You can write BFS from memory in <5 minutes, including correct visited-on-enqueue semantics.
• You can write DFS recursively and iteratively (with explicit stack) from memory in <8 minutes total.
• You can write Dijkstra from memory in <8 minutes, lazy variant, including the staleness-skip line.
• You can write Kahn’s topological sort from memory in <6 minutes.
• You can write DSU with path compression and union by rank from memory in <5 minutes.
• You can write Kruskal’s MST from memory in <10 minutes (DSU + sort).
• You can recognize “this is a graph problem” within 2 minutes of reading any of the 30 classic graph problems on this list.
• You can correctly choose between BFS / Dijkstra / Bellman-Ford / 0-1 BFS based on edge weights.
• You can model the bus-routes problem (LC 815) as a graph in <5 minutes, articulating the bipartite structure.
• You can model the alien-dictionary problem (LC 269) as a topological sort in <5 minutes, articulating the constraint-extraction step.
• You can articulate the cut property and why it makes Kruskal correct, in <30 seconds.
• You can articulate why Dijkstra fails on negative weights, in <30 seconds.
• You can articulate the white-path lemma and its connection to topological sort via reverse post-order.

Exit Criteria

You may move to Phase 5 (Dynamic Programming) when all of the following are true:

1. You have completed all nine labs in this phase, with the lab’s mastery criteria checked off for each.
2. You have solved at least 40 unaided graph problems from LeetCode (mix of Medium, Medium-Hard, Hard) and reviewed each via REVIEW_TEMPLATE.md.
3. Your unaided success rate on Medium-Hard graph problems is ≥ 70%.
4. In a mock interview (phase-11-mock-interviews/), you correctly identify the algorithm family within 2 minutes for at least 8 of 10 graph problems.
5. You can write Dijkstra, BFS, DFS, Kahn’s topological sort, and DSU + Kruskal — five algorithms — from a blank slate in under 45 minutes total.

If any of these fails, do another 15–25 graph problems before moving on. Skipping this gate calcifies bad habits that compound in Phase 5 (where DP-on-graphs and DAG-DP build directly on this material).

Labs

Hands-on practice. Each lab follows the strict 22-section format from Phase 0.

1. Lab 01 — BFS Shortest Path (Word Ladder)
2. Lab 02 — DFS Connected Components (Number of Islands)
3. Lab 03 — Multi-Source BFS (Rotting Oranges / Walls and Gates)
4. Lab 04 — Dijkstra (Network Delay Time / Cheapest Flights)
5. Lab 05 — Bellman-Ford (Cheapest Flights Within K Stops)
6. Lab 06 — Topological Sort (Alien Dictionary)
7. Lab 07 — Union-Find Applications (Accounts Merge / Provinces)
8. Lab 08 — MST Kruskal (Min Cost to Connect All Points)
9. Lab 09 — Graph Modeling (Bus Routes)

← Phase 3: Advanced Data Structures · Phase 5: Dynamic Programming → · Back to Top