Unit 8 · Heavy
The most general structure in the course, and the one where the choice of representation changes the complexity of everything built on top of it.
What a strong answer looks like
A strong Unit 8 answer names the representation, states complexity in terms of both vertices and edges, and says which traversal discipline the algorithm relies on.
Know
An adjacency list uses space proportional to vertices plus edges; an adjacency matrix uses the square of the vertices regardless of how few edges exist.
Apply
Choose the list for sparse graphs and the matrix when edge lookup between two named vertices must be constant.
Watch out
Quoting a traversal cost without saying which representation it assumes. The answer differs.
Study move
State the space and the traversal cost for one graph under both representations.
Know
BFS uses a queue and expands in layers, so the first time it reaches a vertex it has used the fewest edges. That is why it solves unweighted shortest paths.
Apply
Use BFS when the fewest steps matters and edges carry no weight.
Watch out
Expecting BFS to handle weighted shortest paths. Layer order is not weight order.
Study move
Run BFS on a small graph and record the layer each vertex is discovered in.
Know
DFS uses a stack, explicitly or through recursion, and goes deep before backtracking. It underpins cycle detection and topological ordering.
Apply
Detect a cycle in a directed graph by finding an edge back to a vertex still on the recursion stack.
Watch out
Calling any edge to a visited vertex a cycle. An edge to a finished vertex is legal in an acyclic graph.
Study move
Trace DFS on a directed graph and classify each edge as tree, back, or cross.
Know
Dijkstra settles vertices in increasing distance and therefore cannot tolerate negative edges. Kruskal and Prim build minimum spanning trees by different strategies.
Apply
Choose Bellman-Ford over Dijkstra when negative weights are possible.
Watch out
Running Dijkstra on a graph with negative edges, which finalises a vertex a later edge could still improve.
Study move
Construct a small graph with a negative edge where Dijkstra returns a wrong distance.
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 a campus as a graph where edges carry walking times, choose an algorithm for the fastest route, and justify it against one alternative.
