Graphs, No Gaps
Traversal & Connectivity · Ordering, Partitions & Spanning Structure · Weighted Paths — a complete, prerequisite-ordered path through 31 sub-variants, with Java 21 templates, failure-mode tables, a recognition guide, and per-sub-variant mastery gates.
Calibration: written for an advanced backend engineer doing FAANG prep in Java 21, LeetCode-numbered, and shaped as the third companion to Three Patterns, No Gaps and Trees, No Gaps. The level bracket is left open, so the doc is tiered instead of guessed: the ★ core path is the minimum sufficient set (a strong beginner can follow it linearly), ○ marks optional depth, and the ○ problems double as the Extra Reps / transfer-test pool — skip them if the starred problem in the same sub-variant went clean the first time.
Total core: 64 problems — 54 ★ plus 10 ⚠︎, out of 104 listed. This is the library convention: ★ and ⚠︎ are both must-solve, and the bundle card in the library index reports the ★ figure with ⚠︎ shown beside it, exactly as Bundles 01 and 02 do. Everything else is explicitly labelled optional. Nothing here is padding; if a problem is listed, there is exactly one thing it teaches that no earlier problem taught.
How to read the tables#
| Marker | Meaning |
|---|---|
| ★ | Core. Must solve unaided, from scratch, before advancing. |
| ○ | Optional. Solve only if the gate check for that sub-variant fails, or you want depth. |
| PRO | LeetCode Premium. Free substitute given where one exists. |
| ↻ | Re-solve of a problem already listed elsewhere, under a different machine. Not counted twice. |
| ⚠︎ | Anti-pattern problem. Included specifically because the obvious machine is wrong. These are the highest-value problems in the entire document. |
Problems within a sub-variant are in strict prerequisite order. Sub-variants themselves are in prerequisite order.
Three conventions used throughout, because they remove more bugs than anything else:
- Name the machine before you write code. Every graph question is answered by exactly one of six machines: traverse (DFS/BFS), order (topological sort), partition (DSU), span (MST), relax (Dijkstra/Bellman-Ford/Floyd), or search the answer (binary search or an offline sweep). Saying which one out loud is most of the skill.
visitedis set on push, not on pop. Every wrong-answer-that-looks-right in BFS traces back to this line. Setting it on pop lets the same node enter the queue many times, which turns O(V+E) into something worse and can report a non-minimal distance.- The node is whatever uniquely determines the future. If two situations differ in anything that affects what is reachable from them — remaining budget, keys held, parity of the step count — they are different nodes, and
visitedmust be keyed by all of it.
4 — RECOGNITION GUIDE#
4.1 The decision procedure#
Run these in order. Stop at the first match.
Step 0 — Is there a graph at all? Signals: an edges[][] list, an n × n relation matrix, a grid, a set of strings one edit apart, an array where a[i] is itself an index, a set of prerequisites / equations / dependencies. If the problem names a set of objects and a relation between them, it is a graph. Build the adjacency list before you think about which algorithm to run — half of "hard graph" problems are ordinary BFS in an unfamiliar input format.
Step 1 — Directed or undirected? Say it out loud. It decides cycle detection (parent-skip vs. three colours), whether visited alone is sufficient, and whether topological sort is even legal.
Step 2 — Are the edges weighted?
| Weights | Machine |
|---|---|
| None (every step costs 1) | BFS. Never DFS |
| Non-negative | Dijkstra (§3.A) |
All in {0, 1} | 0-1 BFS with a deque (§3.D) |
| Negative present, or a cap on edge count | Bellman-Ford (§3.E) |
All pairs needed, n ≤ ~400 | Floyd–Warshall (§3.F) |
| Weights exist but you only need "can I connect everything cheaply" | MST (§2.H) |
Step 3 — What is actually being asked?
| Ask | Machine |
|---|---|
| Reachability — "can I get there" | DFS or BFS, either is fine |
| Component count / grouping / merging | DFS component count (§1.E) or DSU (§2.E–G) |
| Shortest path, unweighted | BFS (§1.C/D) |
| Shortest path, weighted | Dijkstra family (§3) |
| All paths, or a count of ways | Backtracking with an undo (§1.I), or DAG DP (§2.D) |
| A valid order / schedule | Topological sort (§2.B/C) |
| "Is there a cycle" | Three colours if directed (§2.A); parent-skip DFS or DSU if not (§1.F) |
| Cheapest set of edges connecting everything | MST (§2.H) |
| Edges whose removal disconnects | Bridges, Tarjan (§2.I) |
| Use every edge exactly once | Eulerian path, Hierholzer (§2.K) |
| The answer is a threshold and feasibility is monotone | Binary search + BFS (§3.G), or an offline DSU sweep (§3.H) |
Step 4 — Is the graph implicit? Grid, board position, word, lock combination, bitmask of collected keys. Do not materialise an adjacency list — write neighbours(state) and let the search call it. The node is whatever uniquely determines the future.
Step 5 — Does the state need augmenting? If the same physical position can be reached twice with a different remaining budget, key set, colour, or parity, then visited keyed by position is a wrong answer, not a slow one. Size the array by the whole tuple.
Step 6 — Is the graph a DAG? If yes: no visited set is needed for path enumeration, memoisation is legal, and the topological order is a valid DP evaluation order. Most "hard graph DP" is a DAG you failed to notice — strict inequalities in the movement rule (329) and "prerequisites" phrasing are the two tells.
Step 7 — Does every node have out-degree exactly 1? nums[i] = j, edges[i] is a single int, "each person points to one other". Functional graph: every component is a rho. Label by visit step rather than running generic cycle detection (§2.J).
Step 8 — Are the queries offline? A batch of queries with thresholds, and no requirement to answer in order. Sort the edges and the queries, sweep once with a DSU, write answers back by original index (§3.H).
4.2 Signal → pattern cheat table#
| Signal in the problem statement | Most likely | Watch out for |
|---|---|---|
| "grid", "islands", "regions", "provinces" | Grid DFS/BFS or DSU | Mark on push |
| "shortest", no weights mentioned | BFS | DFS returns a path, not the shortest |
| "minimum cost / time / effort", non-negative | Dijkstra | Heap of (dist, node), skip stale pops |
| "at most k stops / edges / moves" | Bellman-Ford, k+1 rounds | Dijkstra's finality invariant is void |
| "prerequisites", "order", "dependencies", "before" | Topological sort | Detect the cycle; do not assume a DAG |
| "connected", "groups", "merge", "same set" | DSU | Union by size + path compression, or it is O(n) per find |
| "minimum cost to connect all" | MST | This is not shortest path |
| "maximise the minimum edge on a path" / "minimise the maximum" | Bottleneck Dijkstra, or DSU by sorted weight, or binary search | Three valid solutions — pick deliberately |
| "each node points to exactly one other" | Functional graph | Not generic cycle detection |
"all pairs", n ≤ 400 | Floyd–Warshall | k outermost |
| "remove one edge and the network splits" | Bridges (Tarjan) | Not brute-force removal |
| "use every ticket / every edge once" | Hierholzer | Not plain backtracking |
| "how many ways / how many paths" | DAG DP, or counting during relaxation | Not a shortest-path variant |
| "you may break / remove k walls" | State BFS on (r, c, k) | visited[r][c] is a wrong answer |
| "two groups", "dislikes", "cannot be together" | Bipartite 2-colouring | Loop over all components |
| "strictly increasing path in a matrix" | Memoised DFS on a DAG | No visited set |
| Batch of queries each with a limit | Offline sort + DSU sweep | Answer by original index |
| "cost is 0 if you keep going, 1 if you turn" | 0-1 BFS | Dijkstra also works, one log slower |
"n nodes, edges[i] = [a, b]" and the word "tree" | Tree-as-graph (Bundle 02, §1.F) | There is no root until you pick one |
4.3 Trap cases — where the obvious machine is wrong#
| Problem | The obvious (wrong) read | Why it fails | Correct approach |
|---|---|---|---|
| 797. All Paths From Source to Target | Traversal ⇒ visited set | It is a DAG; a global visited silently drops every path through an already-seen node | Backtracking with no mark at all |
| 261. Graph Valid Tree | Check for a cycle | A forest is acyclic and is not a tree | edges == n − 1 and one component |
| 827. Making A Large Island | Flood fill from every 0 | O((mn)²) | Label islands once with sizes, then sum distinct neighbour ids |
| 802. Find Eventual Safe States | DFS with visited | visited conflates "on the stack" with "proved safe" | Three colours, or Kahn on the reversed graph |
| 269. Alien Dictionary | Edge from every character pair | Only the first differing char of adjacent words is an edge | And reject ["abc","ab"] explicitly |
| 329. Longest Increasing Path | BFS/DFS with visited | Cells are legitimately reused across different paths | Strict increase ⇒ DAG ⇒ memoise |
| 1192. Critical Connections | Remove each edge, recheck connectivity | O(E·(V+E)) | Tarjan low-links, one DFS |
| 332. Reconstruct Itinerary | Lexicographic greedy DFS | The smallest next airport can consume your only exit and strand the walk | Hierholzer: post-order append, then reverse |
| 1631. Path With Minimum Effort | Grid DP | 4-directional movement admits no valid evaluation order | Dijkstra with max relaxation, or binary search + BFS |
| 787. Cheapest Flights Within K Stops | Dijkstra | With a stop budget, the first pop of a node is no longer final | Bellman-Ford, k+1 snapshot rounds |
| 1091. Shortest Path in Binary Matrix | DFS | DFS gives a path, not the shortest | BFS |
Any grid BFS marking visited on pop | "same thing, later" | The same cell enters the queue many times → TLE and non-minimal distances | Mark in the same statement that enqueues |
| Dijkstra with any negative edge | "still a shortest path" | Finality requires non-negative weights | Bellman-Ford |
1293 / 864 with visited[r][c] | "a cell is a cell" | Two arrivals with different budgets are different states | Key visited by the full tuple |
| 128. Longest Consecutive Sequence with DSU | "it's a grouping problem" | Correct but heavier than needed | Hash set, walk up only from sequence starts |
| MST for "shortest path from u to v" | "minimum edges, minimum path" | The MST path between two nodes is often not the shortest | Dijkstra |
5 — MASTERY CHECKPOINTS#
Each gate is pass/fail, no partial credit. Gate conditions are things you do without an IDE, without hints, and without looking at your own notes. A gate you "mostly" pass is a gate you failed.
5.1 Traversal & Connectivity#
| Gate | You may advance when you can... | Fail action |
|---|---|---|
| A → B | Write the grid DFS blind including the four-guard order (bounds, then contents), and state why sinking the cell is a legal substitute for a visited array in 200 but not in 79 | Redo #1–#3 |
| B → C | State the inversion — "mark what escapes, then take the complement" — unprompted, and explain why 417 traverses uphill from the oceans rather than downhill from every cell | Re-derive the complexity of the forward version on paper before touching another problem |
| C → D | Write the level-snapshot BFS blind, and explain in one sentence why marking on pop is wrong rather than merely slow | Redo #11, then hand-trace a 3×3 grid where the pop-marking version reports a larger distance |
| D → E | Seed a multi-source BFS from memory and say what the answer is: the last level, a per-cell distance, or a count | Redo #15–#17 in one sitting; the three answers are the lesson |
| E → F | Turn int[][] edges into List<Integer>[] blind in under two minutes, and reproduce 1466's signed-edge trick without re-deriving | Redo #22 |
| F → G | State both conditions for a tree and produce a 4-node counterexample that is acyclic and not a tree | Redo #27. This is the cheapest gate to fail and the most embarrassing to fail in an interview |
| G → H | Write the 2-colour BFS blind with the outer component loop, and say what a conflict looks like | Redo #28, then run it on a disconnected test you construct yourself |
| H → I | Explain why the clone must enter the map before recursing, using a 2-node cycle | Redo #30 |
| I → J | State the rule "permanent mark for shortest path, undone mark for enumeration, no mark on a DAG" and place 797, 79 and 1091 correctly into it without hesitating | Redo #31 and #32 back to back. If 797 still feels like it needs visited, that is the whole gate |
| J → K | Given a new grid problem with a budget, name the state tuple and the visited dimensions before writing code | The most transferable gate in the pattern. Redo #36, then solve #37 cold |
| K → done | Explain why pattern buckets beat pairwise comparison in 127, and state the termination condition of the two-ended search | Redo #41; if the bidirectional version is unclear, write the one-directional version first and diff them |
5.2 Ordering, Partitions & Spanning Structure#
| Gate | You may advance when you can... | Fail action |
|---|---|---|
| A → B | Write the three-colour DFS blind and say what GREY→BLACK means that GREY→GREY does not | Redo #45, then #46. The pair is the lesson |
| B → C | Write Kahn blind, including the order.size() == n cycle report, in under four minutes | This is the foundation gate. Do not proceed. Rewrite daily until it is muscle memory |
| C → D | Given a prose description of dependencies, produce the node set and the edge set on paper before writing any code, and state the cycle semantics for that domain | Redo #50, then #51 with only the constraints section visible |
| D → E | Explain why 329 needs a memo and not a visited set, in terms of the graph being acyclic | You have the code but not the pattern. Re-derive on paper before touching another problem |
| E → F | Write the DSU class blind — find with path compression, union by size, a components counter decremented in the right branch — in under four minutes with zero compile errors | The second foundation gate. Do not proceed |
| F → G | Given a new grouping problem, say whether the answer is n − components, components − 1, or a per-component aggregate, before coding | Redo #62 and #63 side by side |
| G → H | Explain what union-by-time buys you in 305 that a fresh traversal per step does not | Redo #68 (or its free substitute) and state the complexity of the naive version out loud |
| H → I | State the difference between MST and shortest path in one sentence, and give a 4-node graph where the MST path between two nodes is longer than the shortest path | Redo #73 both ways, Kruskal and Prim, and say which suits a complete graph |
| I → J | Write the bridge DFS blind and correctly justify disc[v] on the back edge and low[v] on the tree edge | Redo #76. Hand-trace a 4-cycle with one pendant edge |
| J → K | Recognise a functional graph from the input signature alone and state why one global pass suffices | Redo #77 |
| K → done | Explain, with a concrete 3-airport counterexample, why lexicographic greedy strands the walk in 332 | Redo #81. If the counterexample does not come to hand, you memorised Hierholzer without understanding it |
5.3 Weighted Paths & Search on the Answer#
| Gate | You may advance when you can... | Fail action |
|---|---|---|
| A → B | Write Dijkstra blind in under five minutes with long distances and the stale-pop skip, and state the finality invariant and its precondition | This is the foundation gate. Do not proceed. Rewrite daily |
| B → C | Change the relaxation from dist[u] + w to max(dist[u], w) and explain why Dijkstra is still correct under it | Redo #87 and #88 back to back, in that order, in one sitting |
| C → D | Given a new problem, decide whether the state needs augmenting before writing code, and name every dimension | Redo #91, then #92. If 1293 (§1.J) does not feel like the same idea, re-read §4.1 Step 5 |
| D → E | Write 0-1 BFS blind and explain why the deque frontier stays monotone | Redo #94, then solve #95 cold in under ten minutes |
| E → F | State — unprompted — exactly which invariant 787 breaks, then write Bellman-Ford blind with the snapshot and explain what happens without it | 787 is the capstone anti-pattern of this bundle. If it fails, run the Dijkstra version against the failing test until you can see the finalisation happen |
| F → G | Write Floyd blind with k outermost and the INF guards, and name the n at which it stops being viable | Redo #97, then #99 |
| G → H | Given any "maximise the minimum" graph problem, produce all three solutions — Dijkstra, binary search + BFS, DSU by weight — and say which you would write in an interview and why | Redo #88 three ways and write the mapping between them explicitly |
| H → done | Explain why sorting the queries is legal, and write the sweep with answers restored to original index order | Redo #103, then #104. If the index restoration is the bug, that is the whole sub-variant |
5.4 Revisit rule for ★ problems#
Log every starred problem with an outcome the moment you finish it. The interval depends only on how you solved it, never on how you felt about it.
| Outcome | Next revisit | Then | Then | Graduates when |
|---|---|---|---|---|
| Clean — unaided, optimal, first submission accepted, ≤ 25 min | +14 days | +45 days | done | 2 consecutive clean runs |
| Slow — unaided and optimal, but > 40 min or multiple failed submissions | +7 days | +21 days | +45 days | 2 consecutive clean runs |
| Hinted — you read a hint, a tag, or the pattern name | +3 days | +10 days | +30 days | 2 consecutive clean runs (slow doesn't count) |
| Solved — you read the editorial or any solution code | +1 day | +4 days | +12 days | 3 consecutive clean runs |
| Suboptimal — accepted but wrong complexity | Treat as Hinted, and additionally re-solve the previous starred problem in the same sub-variant |
Additional rules that matter more than the intervals:
- Name the machine first. On every revisit, say which of the six machines this is — traverse, order, partition, span, relax, search the answer — before opening the editor. Naming it wrong downgrades the attempt to Hinted regardless of how the code goes.
- Say where
visitedis set. Push or pop, and keyed by what. If you cannot answer both parts instantly, the attempt is Hinted. - Blind template first. Write the sub-variant's template from memory before reading the problem. A wrong template downgrades the attempt on its own.
- Two strikes → step back. Any starred problem that fails to reach Clean on two consecutive revisits: stop, go back one sub-variant, re-solve its last two starred problems. The failure is almost always upstream.
- Failure-mode tagging. When a revisit isn't clean, tag it with the row number from the relevant §*.4 table. After ten problems you will have two or three dominant tags — those are your actual weaknesses, and they are worth more than any problem count.
- Draw the graph. Any graph bug that survives two readings of the code gets a hand-drawn 6-node counterexample with exactly one cycle. As with trees, the drawing finds the bug faster than the debugger.
- The sub-variant transfer test. Once per sub-variant, take an unseen ○ problem from the same sub-variant and solve it cold. If the core problems are clean but the transfer fails, you learned the problems, not the pattern.
- Never revisit an unstarred problem unless it is serving as a transfer test.
- Cap the queue at 12 due items. If more than 12 come due, do the oldest 12 and push the rest. A backlog you avoid is worse than an interval you stretch.
Appendix A — Coverage summary#
| Pattern | Sub-variants | ★ core | ⚠︎ (inside core) | Core total | ○ optional | Listed |
|---|---|---|---|---|---|---|
| Traversal & Connectivity | 11 | 24 | 3 (827, 261, 797) | 27 | 17 | 44 |
| Ordering, Partitions & Spanning | 11 | 16 | 5 (802, 269, 329, 1192, 332) | 21 | 17 | 38 |
| Weighted Paths & Search on the Answer | 9 | 14 | 2 (1631, 787) | 16 | 6 | 22 |
| Total | 31 | 54 | 10 | 64 | 40 | 104 |
Premium problems: 12 listed, of which 3 are core (261, 269, 305). Free substitutes are named in the table row for each.
The ten ⚠︎ problems are the highest-value items in the document. They are the only ones that teach you when not to reach for the obvious machine, which is the difference between someone who has done 400 graph problems and someone who can solve an unseen one.
Appendix B — Deliberately out of scope#
Named here so that "no gaps" means what it says. None of these has appeared on a FAANG loop in recent memory; each is one search away if you need it.
| Topic | Why it is out | Know that |
|---|---|---|
| Max flow / min cut (Dinic, Edmonds–Karp) | Effectively untested at this level | Max-flow = min-cut; bipartite matching reduces to it |
| Bipartite matching (Hopcroft–Karp, Hungarian) | Same | Kőnig's theorem links matching to vertex cover |
| Strongly connected components (Kosaraju, Tarjan) | Almost never the intended solution on LeetCode | Condensing a digraph by SCC yields a DAG; that is the one useful fact |
| 2-SAT | Competitive programming only | It is an SCC problem on the implication graph |
| Heavy-light decomposition, centroid decomposition | Competitive programming only | |
| LCA by binary lifting | Appears on trees, not general graphs | Bundle 02 covers the recursive LCA |
| A\* and heuristic search | No LeetCode problem requires the heuristic | It is Dijkstra with f = g + h, admissible h |
| Johnson's algorithm | Superseded by Floyd at the tested input sizes |
Appendix C — Where this bundle connects to the others#
- LC 329 (longest increasing path) is memoised DFS on a DAG — the same "return what composes, record what does not" split as tree recursion, Bundle 02 §2.C.
- LC 2360 (longest cycle in a functional graph) is LC 287's argument from Bundle 01 §1.G with a different termination proof: the array was a linked list there too.
- LC 778 / 1631 / 1102 are binary search on the answer — Bundle 01 §3.G/H — with a BFS standing in for the feasibility predicate. LC 1697 / 2503 are the offline version of the same idea.
- LC 310 (minimum height trees) is topological peeling: the same strip-the-frontier motion as multi-source BFS in §1.D, run on degree instead of distance.
- LC 863 (all nodes distance K, Bundle 02 §1.F) is a tree converted into an undirected graph — which is Step 0 of §4.1 here, arriving from the other direction.
- LC 133's
Map<Node, Node>is LC 138's random-pointer map:visitedand the memo being the same object is a pattern, not a coincidence. - LC 787 breaks Dijkstra for exactly the reason a non-monotone
feasible(x)breaks binary search in Bundle 01 §4.3: the algorithm's correctness rests on an invariant, and the problem quietly removes it.
If those seven sentences read as obvious, the patterns have transferred. If any of them reads as a surprise, that is the next thing to study.