Unit 6 · Heavy
The most general structure, and the one where representation choice changes the complexity of everything built on it. Many problems that do not look like graphs become easy once modelled as one.
Know
Recognising a graph problem is often the whole difficulty. States and transitions, dependencies, and relationships all become vertices and edges.
Apply
Define what a vertex is and what an edge means before choosing an algorithm.
Watch out
Missing that a puzzle is a shortest-path problem over states, and writing a bespoke search instead.
Know
BFS uses a queue and finds fewest-edge paths; DFS uses a stack and underpins cycle detection and topological order.
Apply
Choose BFS for unweighted shortest paths and DFS for structural questions.
Watch out
Calling any edge to a visited vertex a cycle. Only an edge to a vertex still on the recursion stack closes one.
Know
Dijkstra settles vertices in increasing distance, which negative edges invalidate. Bellman-Ford relaxes repeatedly and tolerates them.
Apply
Check the weight assumption before choosing.
Watch out
Running Dijkstra with negative weights, which finalises a vertex a later edge could still improve.
Know
Kruskal adds globally cheapest safe edges using union-find; Prim grows one tree. Topological order exists only for directed acyclic graphs.
Apply
Use topological order to sequence dependencies, and detect the cycle that makes it impossible.
Watch out
Attempting a topological sort on a graph containing a cycle, which has no valid answer.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Model course prerequisites as a graph, produce a valid study order, and explain what a cycle in the data would mean.
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic