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.
What a strong answer looks like
A strong Unit 6 answer names the representation, gives complexity in both vertices and edges, and states which precondition the chosen algorithm needs.
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.
Study move
Model a word-transformation puzzle as a graph and name the vertices and edges.
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.
Study move
Run both traversals on one graph and compare the visit orders.
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.
Study move
Build a small graph with a negative edge where Dijkstra is wrong.
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.
Study move
Topologically order a dependency graph and say what a cycle would mean in context.
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.
