Chapter 20
Elementary Graph Algorithms
20.1 representations · 20.2 breadth-first search · 20.3 depth-first search · 20.4 topological sort · 20.5 strongly connected components.
Start vertex: A
Adjacency-list representation
This undirected graph stores each edge at both endpoints.
An adjacency matrix instead uses Θ(V²) space and supports O(1) edge-existence tests; lists are preferable for sparse graphs.
BFS uses a FIFO queue. First discovery of a vertex gives a shortest path measured in number of edges.
DFS uses a stack (or recursion). Entry/exit times expose structure such as back edges and components.
20.4–20.5 · Topological sort & strongly connected components
Topological sort uses a DAG; the SCC example includes cycles to show nontrivial components.
Ready
DFS finishing times give a topological ordering on a DAG. Kosaraju’s algorithm runs DFS, reverses every edge, then explores in decreasing finishing-time order.
Chapter 21
Minimum Spanning Trees
21.1 grows a tree across a cut; 21.2 compares Kruskal’s edge ordering with Prim’s frontier expansion.
Ready
Kruskal considers edges from lightest to heaviest and joins different components (disjoint-set union). Prim grows one tree by repeatedly taking its lightest outgoing edge.
* With a binary heap and adjacency lists. The selected tree’s total weight is reported at completion.
Chapter 22
Single-Source Shortest Paths
22.1 Bellman–Ford · 22.2 DAG paths · 22.3 Dijkstra · 22.4 difference constraints · 22.5 shortest-path properties.
Ready · source A
Dijkstra finalizes the nearest unsettled vertex and requires nonnegative weights. Bellman–Ford allows negative edges and detects reachable negative cycles. A DAG can be solved in topological order, even with negative weights.
A constraint xᵥ − xᵤ ≤ w becomes edge u→v of weight w. Add a zero-weight super-source; a negative cycle means the system is infeasible.
Shortest-path correctness follows from relaxation: after a vertex’s shortest path is fully processed, its distance cannot improve. With no reachable negative cycle, repeated relaxation converges to the true distances.
Chapter 23
All-Pairs Shortest Paths
23.1 min-plus matrix multiplication · 23.2 Floyd–Warshall · 23.3 Johnson for sparse graphs.
Ready
Floyd–Warshall allows vertices one at a time as intermediates: dᵏᵢⱼ = min(dᵏ⁻¹ᵢⱼ, dᵏ⁻¹ᵢₖ + dᵏ⁻¹ₖⱼ), in Θ(V³) time and Θ(V²) space.
Min-plus DP extends path length by one edge per round. Johnson uses Bellman–Ford potentials to reweight edges nonnegative, then runs Dijkstra from each vertex; it handles negative edges but no negative cycles.
Chapter 24
Maximum Flow
24.1 flow networks · 24.2 Ford–Fulkerson · 24.3 bipartite matching as a flow problem.
Ready · source S · sink T
This demo uses breadth-first augmenting paths (Edmonds–Karp). Each path pushes its bottleneck; when no residual path remains, the flow is maximum. Runtime is O(VE²). A bipartite matching reduces to flow by giving source-to-left and right-to-sink edges capacity 1.
Chapter 25
Matchings in Bipartite Graphs
25.1 augmenting paths · 25.2 stable marriage · 25.3 minimum-cost assignment with the Hungarian algorithm.
25.1 · Maximum bipartite matching
An augmenting path alternates between unmatched and matched edges; flipping its edges increases matching size by one.
Ready
25.2 · Stable marriage
Gale–Shapley deferred acceptance: unmatched proposers ask their next choice; receivers keep their preferred offer and reject the rest.
Ready
25.3 · Hungarian algorithm
For this square cost matrix, dual potentials maintain nonnegative reduced costs; shortest augmenting paths produce a minimum-cost assignment in O(n³).
Ready