Phase 3 — Graphs & Search¶
Weeks 18–24 | November 30, 2026 – January 11, 2027
Every useful data structure you’ve learned so far is a special case of a graph. A linked list is a directed graph with in-degree ≤ 1 everywhere. A tree is a connected acyclic undirected graph. A BST is a rooted tree with an ordering constraint. Graphs are the general form of all of them, which is why mastering graphs means your earlier intuitions transfer and extend rather than getting replaced.
The fear people bring into this phase is usually: “there are so many algorithms.” There are, but most of them are BFS or DFS with one additional idea layered on top. Dijkstra is BFS on a priority queue. Topological sort is DFS with a finish-time stack. Kruskal’s MST is a sorted edge scan using Union-Find. Once you see those as BFS/DFS + bookkeeping, the phase becomes manageable.
The hard part isn’t memorizing the algorithms. It’s learning to model problems as graphs in the first place. That skill — “this problem is a graph in disguise” — is what separates candidates who reliably ace graph interviews from those who only succeed when the graph structure is handed to them explicitly.
Why Graphs Matter¶
Graphs appear in:
Dependency systems: build tools, package managers, course prerequisites
Network routing: IP routing tables, shortest path in maps
Social networks: friend recommendations, influence propagation
State machines: game states, parsing, compiler flow analysis
Grid problems: flood fill, island counting, maze solving — grids are implicit graphs
If you can model a problem as a graph and apply the right traversal, you’ve reduced a novel problem to a solved one. That’s the leverage.
Common Fear Points (With Honest Responses)¶
“There are too many algorithms.” You need to own 6: BFS, DFS, Dijkstra, Union-Find, Topological Sort, and either Kruskal’s or Prim’s for MST. Everything else is derived from these.
“I don’t know when to use which algorithm.” The algorithm choice follows from what you need: shortest path in unweighted graph → BFS. Shortest path with positive weights → Dijkstra. Dynamic connectivity → Union-Find. Linear ordering of dependencies → Topological Sort. After enough problems, the mapping becomes reflexive. The reference table below is your scaffold until then.
“Graph code has too many details.” Graph code is verbose because you’re managing: the graph structure, the visited set, and whatever state you’re computing. None of these is hard individually. The discipline is keeping them separate in your head. Read each algorithm file once carefully, implement it once from scratch, and the details compress into muscle memory.
Algorithm Reference Table¶
Algorithm |
Use Case |
Time Complexity |
Space |
Common Mistake |
|---|---|---|---|---|
BFS |
Shortest path, unweighted; level-order |
O(V + E) |
O(V) |
Single BFS misses disconnected components |
DFS |
Connected components, cycle detection, topological sort |
O(V + E) |
O(V) |
Directed cycle detection needs 3-color, not just visited |
Dijkstra |
Shortest path, non-negative weights |
O((V+E) log V) |
O(V) |
Fails silently on negative edge weights |
Bellman-Ford |
Shortest path with negative edges, negative cycle detection |
O(V × E) |
O(V) |
V-1 iterations, not V; inner loop over all edges |
Floyd-Warshall |
All-pairs shortest path |
O(V³) |
O(V²) |
DP update order: k (intermediate) in outermost loop |
Union-Find |
Dynamic connectivity, MST (Kruskal) |
O(α(n)) amortized |
O(V) |
Forgetting to do both path compression AND union by rank |
Topological Sort |
DAG ordering, dependency resolution |
O(V + E) |
O(V) |
If not all V in result, graph has a cycle |
Kruskal’s MST |
Minimum spanning tree |
O(E log E) |
O(V) |
Not sorting edges first |
Prim’s MST |
Minimum spanning tree (dense graphs) |
O((V+E) log V) |
O(V) |
Not updating priority queue when shorter path found |
What You’ll Have at the End of This Phase¶
By the end of Week 24 you can:
Look at a problem description and identify within 3 minutes which graph algorithm is relevant
Implement BFS, DFS, Dijkstra, Union-Find, and Topological Sort from scratch without reference, under timed conditions
Debug graph code by reasoning about the traversal state, not just re-reading the algorithm
Model non-obvious problems (word ladder, number of islands, course schedule) as graphs before writing any code
Distinguish between directed and undirected cycle detection without confusing the techniques