Chapter 17 — Advanced Graphs
Source:
src/main/kotlin/graph/flow_network/,src/main/kotlin/graph/tsp/,src/main/kotlin/tree/mst/, and thegraph/rootMaster idea: beyond BFS/DFS (Chapter 6) lie the optimization graph problems: flow networks (how much can travel through a capacitated graph?), bipartite matching (assignments with conflicts), minimum spanning trees (connect everything cheaply), TSP (visit everything optimally), and the state-space BFS tricks (bitmask states, edge weights as graph labels).
Prerequisites: BFS/DFS from Chapter 6, DP from Chapter 2 (Held-Karp), bitmasks from Chapter 16, and heaps from Chapter 7 (Prim’s).
Problems at a glance (this chapter’s core set)
| # | Problem | Pattern | Complexity | Page |
|---|---|---|---|---|
| 17.1 | Max Flow (Edmonds-Karp) | BFS augmenting paths | $O(VE^2)$ | → |
| 17.2 | Maximum Bipartite Matching | Kuhn’s augmenting path | $O(VE)$ | → |
| 17.3 | Min Cost To Connect All Points | Prim’s MST | $O(n^2 \log n)$ | → |
| 17.4 | Travelling Salesman (Held-Karp) | bitmask DP | $O(n^2 2^n)$ | → |
| 17.5 | Shortest Path Visiting All Nodes | BFS over bitmask states | $O(n \cdot 2^n)$ | → |
| 17.6 | Reorder Routes To City Zero | directed-edge DFS | $O(n)$ | → |
| 17.7 | Evaluate Division | edge-labeled graph BFS | $O(Q \cdot E)$ | → |
| 17.8 | Bellman-Ford | V-1 relaxations + cycle check | $O(VE)$ | → | | 17.9 | Reconstruct Itinerary | Hierholzer (Eulerian path) | $O(E log E)$ | → | | 17.10 | Critical Connections In A Network | Tarjan bridges | $O(V+E)$ | → | | 17.11 | Walls And Gates | multi-source BFS distances | $O(mn)$ | → | | 17.12 | Bus Routes | stop→bus two-layer BFS | $O(BS)$ | → | | 17.13 | Minimum Genetic Mutations | 4-neighbor BFS, bank as visited | $O(n)$ | → | | 17.14 | Find Articulation Points | Tarjan low-link | $O(V+E)$ | → | | 17.15 | Longest Path Different Adjacent | char-constrained tree DP | $O(n)$ | → | | 17.17 | Floyd-Warshall | all-pairs DP | $O(n^3)$ | → | | 17.18 | Maximum Vacation Days | week-by-week DP | $O(c^2w)$ | → |
The rest of the graph/ directories
flow_network/ also holds several Edmonds-Karp variants and BipartileMatching.kt (the same Kuhn’s algorithm as 17.2). tsp/ adds ShortestPathVisitingAllNodes.kt (17.5), the brute-force and top-down TSP versions, and TravellingSalesmanRecursiveDP.kt. tree/mst/ adds the Kruskal version of 17.3 (6.6 already covers it). graph/ also has articulation points, SCC, topological sorts, chromatic number, and more.
New pages are appended to the table above as they’re written.