Graph Algorithms

Big Tech Interview Prep · 2 hrs/day · 5 days/week · Java

Week 1 — Fundamentals

Graph Representation

Adjacency list vs matrix vs edge list · when to use each

Breadth-First Search

Ring traversal · shortest path (unweighted) · multi-source

Depth-First Search

Recursive & iterative · pre/post-order · backtracking

Connected Components

Traversal in a loop · labeling · flood fill

Fundamentals Consolidation

Synthesis · recall drills · timed redo · exit check

Week 2 — Shortest Path + Union-Find

Bellman-Ford & 0-1 BFS

Edge relaxation · V−1 passes proof · negative cycles · deque trick

Dijkstra & Floyd-Warshall

Greedy correctness · why negatives break it · all-pairs DP

Basic Union-Find

Disjoint sets · forest representation · the equivalence invariant

Union by Rank + Path Compression

Shallow trees · flattening · the O(α(n)) inverse-Ackermann bound

Union-Find Applications

Cycle detection · Kruskal prep · grouping/merging entities

Week 3 — Topological Sort + MST

Kahn's Algorithm (BFS Topo)

In-degree peeling · cycle-via-count · dependency ordering variances

DFS Topo + Cycle Detection

Finish-time ordering · 3-color marking · directed cycle variances

Global greedy · cut-property proof · MST disguises

Grow-a-tree · Kruskal vs Prim · dense-graph variances

Topo + MST Consolidation

Recognition flowchart · master variance cheat-sheet · exit check

Week 4 — Advanced

Bipartite Check

2-coloring · König's odd-cycle theorem · two-group variances

disc/low-link · single-pass SCCs · 2-SAT & condensation variances

Bridges & Articulation Points

Low-link criticality · > vs ≥ · single-point-of-failure variances

A* Search & Eulerian Path

Admissible heuristics · Hierholzer · itinerary/de Bruijn variances

Network Flow + Full Review

Edmonds-Karp · max-flow min-cut · master recognition table · capstone

See SCHEDULE.md for the full 4-week plan and progress tracker.