Chapter 6 — Graphs
Source:
src/main/kotlin/graph/(the biggest folder in the codebase)Master idea: a graph is vertices + edges — and every problem is one of a handful of engines (BFS, DFS, topological sort, Union-Find, Dijkstra, MST, SCC) started with the right fuel. Trees from Chapter 5 are just graphs with no cycles and one connected component.
Prerequisites: recursion, the level-fencing BFS from 5.2, and a willingness to think in states, not nodes.
Problems at a glance (this chapter’s core set)
| # | Problem | Pattern | Complexity | Page |
|---|---|---|---|---|
| 6.1 | Word Ladder | BFS on an implicit graph | $O(n \cdot L \cdot 26)$ | → |
| 6.2 | Clone Graph | DFS + memo map | $O(V+E)$ | → |
| 6.3 | Course Schedule II | Kahn’s topological sort | $O(V+E)$ | → |
| 6.4 | Is Graph Bipartite | BFS 2-coloring | $O(V+E)$ | → |
| 6.5 | Cheapest Flights With K Stops | Dijkstra + stop budget | $O(E \log E)$ | → |
| 6.6 | Min Cost To Connect All Points | Kruskal MST + Union-Find | $O(n^2 \log n)$ | → |
| 6.7 | Strongly Connected Components | Kosaraju (two DFS passes) | $O(V+E)$ | → |
| 6.8 | Alien Dictionary | DFS topo with cycle detection | $O(V+E)$ | → | | 6.9 | Redundant Connection | Union-Find cycle detection | $O(E α(n))$ | → | | 6.10 | Flood Fill | grid DFS/BFS | $O(mn)$ | → | | 6.11 | The Earliest Moment Everyone Became Friends | DSU with a components counter | $O(E α(n))$ | → | | 6.12 | Network Delay Time | pure Dijkstra | $O(E log V)$ | → | | 6.13 | Word Ladder II | BFS distances + DFS paths | $O(26Ln)$ | → | | 6.14 | Rotting Oranges | multi-source BFS | $O(mn)$ | → | | 6.15 | Accounts Merge | Union-Find over emails | $O(Eα)$ | → | | 6.16 | Surrounded Regions | border BFS marking | $O(mn)$ | → | | 6.17 | Max Area Of Island | sink-and-count DFS | $O(mn)$ | → | | 6.18 | Pacific Atlantic Water Flow | reverse-flow BFS | $O(mn)$ | → | | 6.19 | Find Length Of Longest Cycle | 3-color DFS + distances | $O(n)$ | → | | 6.20 | Making A Large Island | island IDs + neighbor sum | $O(n^2)$ | → | | 6.21 | Number Of Islands II | online Union-Find | $O(kα)$ | → | | 6.22 | Island Perimeter | exposed-edge count | $O(mn)$ | → | | 6.23 | N-Coloring Greedy | greedy vertex coloring | $O(V+E)$ | → | | 6.25 | Sliding Puzzle | board-state BFS | $O(6!)$ | → | | 6.26 | Shortest Bridge | DFS + multi-source BFS | $O(n^2)$ | → | | 6.27 | The Maze III | Dijkstra with lexicographic paths | $O(mn log mn)$ | → | | 6.28 | Optimize Water Distribution | MST + virtual node | $O((n+e)log n)$ | → | | 6.29 | Cracking The Safe | de Bruijn / Hierholzer | $O(k^n)$ | → | | 6.30 | Shortest Distance From All Buildings | multi-source BFS | $O(BRC)$ | → | | 6.31 | Shortest Path With Obstacles Elimination | BFS over (r,c,k) | $O(RCk)$ | → | | 6.32 | Maximum Path Quality | budgeted DFS | $O(2^T)$ | → | | 6.33 | Path With Maximum Probability | max-Dijkstra | $O(e log n)$ | → | | 6.34 | Longest Increasing Path In A Matrix | memoized grid DFS | $O(mn)$ | → |
The rest of the graph/ directory
src/main/kotlin/graph/ is enormous: topological_sort/ (Course Schedule I/II, Parallel Courses), scc/ (Kosaraju), mst/ (Kruskal & Prim on points), flow_network/ (Edmonds-Karp max flow), tsp/ (Travelling Salesman via Held-Karp), euler/ (Cracking The Safe), articulation_point/, cycle/, components/, dag/, dp/, greedy/, plus standalone classics — Word Ladder II, Clone Graph, Bipartite (BFS/DFS variants), Bus Routes, Evaluate Division, Reorder Routes, Minimum Genetic Mutations, Maximum Path Quality, N-Coloring, Chromatic Number, Graph Diameter, House Robber III, and more.
New pages are appended to the table above as they’re written.