Week 13 — Advanced Graphs
Month 3 — Graphs & DP Deep · Week 1 of 4
5 problems, p66–p70. Topics: Minimum Spanning Tree (Kruskal + Prim), bipartite graphs (2-coloring), bridges & articulation points (Tarjan), constrained topological sort over inferred edges (Alien Dictionary), and Eulerian paths (Hierholzer). Each lifts you out of “BFS/DFS” comfort zone into algorithms with subtle invariants and named papers.
Why this week
Weeks 11–12 covered foundational graphs (BFS, DFS, Dijkstra, Bellman-Ford, Union-Find). This week is the named-algorithm tier: MST, Tarjan, Hierholzer. Each has a one-paragraph correctness proof you must be able to state. Senior+ interviews ask for these by reputation — even when not strictly required.
Schedule (Mon–Fri)
| Day | Problem | Focus | Difficulty |
|---|---|---|---|
| Mon | p66 — Min Cost to Connect All Points | MST: Kruskal (sort + DSU) vs Prim (heap) | Medium |
| Tue | p67 — Is Graph Bipartite? | 2-coloring via BFS / DFS, odd-cycle witness | Medium |
| Wed | p68 — Critical Connections in a Network | Tarjan’s bridge algorithm: disc + low | Hard |
| Thu | p69 — Alien Dictionary | Char graph from adjacent word diffs + topo sort + cycle | Hard |
| Fri | p70 — Reconstruct Itinerary | Hierholzer’s algorithm (Eulerian path) | Hard |
Readiness gate (move to Week 14 when)
- Implement Kruskal and Prim cold; explain when each is preferred.
- State Tarjan’s bridge invariant:
low[v] = min(disc[v], low[child], disc[neighbor through back-edge]). - Construct edge cases for Alien Dictionary: prefix-violation (
["abc","ab"]→ “”), cycle. - Explain Hierholzer: why DFS with post-order append yields the Eulerian path.
- Solve all 5 cold in their target windows (25–40 min each).