Chapter map

Where this sits in CS 300. Chapter 10 is the abstraction-substrate chapter. Every previous data structure in this course is really a specialization of a graph: a linked list is a path, a tree is a connected acyclic graph, a heap is a tree with an ordering, a hash-chained bucket is a forest. Chapter 10 turns that specialization upside down --- we work directly with the most general model of “structured connections” and learn the algorithms that live on it: shortest paths, scheduling, dependency resolution, MST, all-pairs distances, strongly connected components. Builds on ch. 6 (BSTs are connected acyclic graphs), ch. 7 (the priority queue is the substrate Dijkstra rides on), and ch. 9 (parent-pointer trees are exactly what BFS and DFS emit).

What you add to your toolkit:

Two graph representations and when to pick which: adjacency list for sparse graphs ( $O(V+E)$ space, $O(\deg u)$ neighbour scan), adjacency matrix for dense or all-pairs work ( $O(V^2)$ space, $O(1)$ edge query). The first question to ask about any graph algorithm is “what does this cost on a sparse input?”
BFS as “shortest paths in unweighted graphs” plus the layer-monotonicity argument that proves it. BFS is the unique algorithm whose frontier ordering equals its correctness proof.
DFS plus edge classification (tree / back / forward / cross). One simple DFS run, four downstream algorithms: cycle detection (back edge $\Rightarrow$ cycle), topological sort (post-order reversal), strongly connected components (Kosaraju’s two-pass), articulation points (tree-edge / back-edge interplay).
Relaxation as the universal SSSP primitive. Dijkstra, Bellman-Ford, and DAG-relax are all instances of “relax every edge in some order; correctness comes from the order.” Internalise the primitive and the three algorithms collapse to one.
Cut and cycle properties as the structural lemmas that justify both Kruskal and Prim --- the same proof carrying two different greedy implementations.
Algorithm selection at a glance: given a problem (single-pair / single-source / all-pairs / MST / topo / cycle / SCC) and graph properties (unweighted / non-negative / negative-no-cycle / negative-with-cycle / DAG / sparse / dense), pick the right algorithm in one sentence. Master decision table is §10.15.

Mastery checklist --- you should be able to, without references:

State the BFS algorithm + sketch why it produces shortest paths in unweighted graphs (§10.5 layer-monotonicity argument: queue contents are $\{d, \ldots, d, d+1, \ldots\}$ stretches, alternative paths would have surfaced earlier and shorter).
Run DFS on a 6-node directed graph by hand, classifying every edge as tree / back / forward / cross + identifying the topological sort from post-order (§10.6 + §10.11).
State relaxation + argue why it is monotonic + sketch why one round of relaxation over all edges in topological order solves DAG shortest paths in $O(V+E)$ (§10.8 universal-SSSP-primitive framing).
State Dijkstra’s algorithm + why it requires non-negative edge weights, with a one-line counterexample on a 3-node graph with a negative edge (§10.9 greedy-correctness argument + §10.9 negative-edge counterexample).
State Bellman-Ford’s $|V|-1$ -round relaxation correctness (induction on path length) + describe negative-cycle detection (one extra round; any further relaxation $\Rightarrow$ reachable negative cycle), per §10.10.
State the cut property + cycle property + use them to argue both Kruskal and Prim produce a minimum spanning tree (§10.12).
Pick the right algorithm for a shortest-path problem at first sight: unweighted $\to$ BFS, DAG $\to$ DAG-relax, non-negative-weighted $\to$ Dijkstra, negative weights $\to$ Bellman-Ford, all-pairs $\to$ Floyd-Warshall (or Johnson for sparse). Justify each choice in one sentence (§10.15 master decision table).

Looking ahead. Chapter 11 introduces B-trees as the shallow-and-wide alternative to ch. 9’s balanced BSTs --- filesystems and database indices use B-trees because the disk-page / SSD-block geometry rewards high fan-out, and the underlying graph-flavoured pointer structure is the same one we manipulate here. Chapter 12 covers the set ADT in full; the visited / discovered sets that BFS and DFS rely on are exactly the “does the set contain $x$ ?” interface ch. 12 formalises. Forward direction (not in cs-300): A* (Dijkstra + heuristic, §10.16 notebox), Johnson’s algorithm (sparse all-pairs, §10.16), network flow (Ford-Fulkerson + Edmonds-Karp, CLRS Ch 26), planar graphs (4-colour theorem, planarity testing).

10.1 Introduction

The vocabulary

The shape of the space

A graph has up to $\binom{V}{2} = \Theta(V^2)$ possible edges (undirected) or $V(V-1) = \Theta(V^2)$ (directed). The real world rarely fills that space:

Dense graph: $|E| = \Theta(V^2)$ . Every vertex is connected to a constant fraction of the others. Complete graphs, small road networks within a city block.
Sparse graph: $|E| = O(V)$ or $O(V \log V)$ . Each vertex has only a few neighbors. Most real graphs: social networks, road networks, computer networks, the web.

Dense vs. sparse matters enormously for algorithm choice. An $O(V^2)$ algorithm on a sparse graph is wasteful; an $O(E \log V)$ algorithm is brilliant on sparse graphs and mediocre on dense ones. The first question to ask about any graph algorithm is: “what does this cost on a sparse input?”

The picture

Vocabulary is easier to keep straight if you can see it. The same five vertices below carry an undirected and a directed edge set; note how “degree” splits into “in-degree” and “out-degree” once edges acquire direction.

::: center :::

Left (undirected): vertex $b$ has degree $3$ --- neighbours $\{a, c, e\}$ . Path $a$ — $d$ — $e$ — $b$ has length $3$ (unweighted).

Right (directed): vertex $b$ has in-degree $2$ (edges from $a$ and $e$ ) and out-degree $1$ (edge to $c$ ). Vertex $a$ is a source (in-degree $0$ ); vertex $c$ is a sink (out-degree $0$ ). The directed path $a \to d \to e \to b \to c$ has length $4$ .

10.2 Applications

The textbook section runs through three examples; the interesting claim is the same in each:

Navigation (geography)

Cities/intersections are vertices; roads are edges. Edge weights are distances or travel times. Shortest-path queries give driving directions. This is what powers Google Maps, Waze, and every GPS unit made since the 90s.

The interesting twist: edge weights aren’t static. Real-time traffic turns the same road into a different edge every few minutes. The right algorithm has to be fast enough that you can re-solve every time conditions change, not just once.

Product recommendations (e-commerce)

Products are vertices; “bought together” or “viewed together” is an edge. A customer’s basket gives you a starting set; walk one step out along the edges and you have recommendations.

Social and professional networks

People are vertices; relationships are edges. “Friends of friends” is a two-step walk. PageRank, centrality, community detection all live here.

Other common models you’ll encounter

Compiler dependencies. Source files are vertices, #include edges drive rebuild order — a topological sort of the dependency DAG.
Spreadsheet formula dependencies. Cells are vertices, references are edges. Evaluation order is a topological sort; circular references are a cycle detection problem.
Package managers. Libraries are vertices, dependency constraints are edges. Resolving versions is a constraint problem on the graph.
Build systems (make, bazel, cmake). Targets are vertices, prerequisites are edges. Determining what to rebuild after a change is reachability.
State machines. States are vertices, transitions are edges. Model checking is graph reachability with labels.
Game AI and pathfinding. Tiles or waypoints are vertices, valid moves are edges. A* (shortest path with a heuristic) is the industry standard.
Neural networks. The topology is literally a weighted DAG.

10.3 Adjacency Lists

We have the vocabulary. Now: how do we store a graph in memory?

C++ representations

Several idioms are common; pick based on your data model.

// 1. Vertices as integer IDs 0..V-1, parallel array of neighbor vectors.
//    The fastest and most common choice in competitive programming.
std::vector<std::vector<int>> adj(V);
adj[u].push_back(v);   // add edge u--v
adj[v].push_back(u);   // undirected => add to both lists

// 2. Weighted edges: store (neighbor, weight) pairs.
std::vector<std::vector<std::pair<int,int>>> adj(V);
adj[u].emplace_back(v, weight);

// 3. Vertex objects with owned adjacency data (OOP style).
struct Vertex {
    std::string label;
    std::vector<Vertex*> neighbors;
};

Cost analysis

Space: $O(V + E)$ . Each vertex’s list contributes one header; each edge contributes two list entries (one in each endpoint’s list for undirected graphs).
“Is $u$ adjacent to $v$ ?”: $O(\deg(u))$ . Scan $u$ ‘s list. Worst case $O(V)$ if $u$ is connected to everything.
“List all neighbors of $u$ ”: $O(\deg(u))$ . Perfect — you just hand over the list.
Add/remove edge: $O(1)$ to add. Removal is $O(\deg(u))$ because you have to find the entry.

Adjacency set vs. adjacency list. MIT 6.006 prefers an adjacency set: a Python set per vertex (or an std::unordered_set<int> per vertex in C++). The trade-off is on the “is $u$ adjacent to $v$ ?” query:

Adjacency list (vector of neighbours): edge query is $O(\deg u)$ scan; iteration is cache-friendly + $O(\deg u)$ .
Adjacency set (hash set of neighbours): edge query is $O(1)$ expected; iteration is $O(\deg u)$ with worse constants (hash-bucket walk).

In competitive programming and most production C++ the list form wins on constants for small/medium $\deg u$ --- BFS, DFS, Dijkstra all rely on neighbour iteration, not on point edge queries. Reach for the set form when the algorithm asks “is $(u,v)$ an edge?” many times and the graph is too sparse to justify a matrix. The chapter from here on uses the list form.

10.4 Adjacency Matrices

std::vector<std::vector<int>> m(V, std::vector<int>(V, 0));
m[u][v] = 1;
m[v][u] = 1;   // undirected

// Weighted version; INT_MAX = "no edge"
std::vector<std::vector<int>> w(V, std::vector<int>(V, INT_MAX));
w[i][i] = 0;   // zero distance to self
w[u][v] = weight;

Cost analysis

Space: $\Theta(V^2)$ . Forgiving for small dense graphs, catastrophic for large sparse ones.
“Is $u$ adjacent to $v$ ?”: $O(1)$ . Just read the matrix cell.
“List all neighbors of $u$ ”: $O(V)$ . Scan row $u$ even if there are only two neighbors.
Add/remove edge: $O(1)$ .
Matrix math: $M^k[i][j]$ is the number of length- $k$ walks from $i$ to $j$ . This is the basis of matrix-multiplication shortest-path algorithms and a ton of algebraic graph theory.

When to pick which

::: center Adjacency list Adjacency matrix

Space $O(V+E)$ $\Theta(V^2)$ Edge query $(u,v)?$ $O(\deg u)$ $O(1)$ List neighbors of $u$ $O(\deg u)$ $O(V)$ Iterate all edges $O(V+E)$ $O(V^2)$ Good for… sparse, large $V$ dense, small $V$ :::

10.5 Breadth-First Search

Algorithm

void bfs(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<bool> discovered(adj.size(), false);
    std::queue<int> frontier;

    frontier.push(start);
    discovered[start] = true;

    while (!frontier.empty()) {
        int u = frontier.front(); frontier.pop();
        visit(u);
        for (int v : adj[u]) {
            if (!discovered[v]) {
                discovered[v] = true;
                frontier.push(v);
            }
        }
    }
}

Distance and parent tracking

BFS’s real power isn’t just “visit everything.” It computes shortest paths in unweighted graphs for free. Augment each visited vertex with a distance and a parent pointer:

void bfs(const std::vector<std::vector<int>>& adj, int start,
         std::vector<int>& dist, std::vector<int>& parent) {
    int n = adj.size();
    dist.assign(n, -1);
    parent.assign(n, -1);
    std::queue<int> q;
    q.push(start);
    dist[start] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }
}

After BFS, dist[v] is the minimum number of edges from start to v; following parent pointers back from v reconstructs the path in reverse.

Cost

$O(V + E)$ . Each vertex is dequeued once; each edge is scanned at most twice (once from each endpoint, for undirected graphs). Can’t be beat for unweighted shortest paths.

Why BFS works – the invariant

Layer-monotonicity proof. Define $L_d = \{v : \texttt{dist}[v] = d\}$ as the set of vertices at distance $d$ from the source. Claim: BFS discovers vertices in non-decreasing order of distance --- the queue is at all times a non-decreasing sequence of dist values spanning at most two consecutive layers.

Induction on $d$ . [Base]{.smallcaps} ( $d = 0$ ): the source is pushed first, with $\texttt{dist} = 0$ , and the queue holds only $L_0$ . [Step]{.smallcaps} ( $d \to d{+}1$ ): suppose the invariant holds when the first $L_d$ -vertex is about to be popped, so the queue is $L_d \mathbin\Vert L_{d+1}^{\text{partial}}$ . Popping a $u \in L_d$ and scanning its neighbours either finds an already-discovered vertex (skip) or an undiscovered $v$ . Any neighbour of $u$ has $\texttt{dist}[v] \le \texttt{dist}[u] + 1 = d + 1$ . If $\texttt{dist}[v] < d+1$ it would already be discovered (the source would have reached it via a shorter path, processed earlier under the IH). So $\texttt{dist}[v] = d+1$ , $v$ joins the back of the queue, and the invariant is preserved.

The invariant immediately gives shortest paths: when $v$ is first discovered, the assignment $\texttt\{dist\}[v] = \texttt\{dist\}[u] + 1$ records the smallest possible distance because any shorter path would have made $v$ visible from a shallower layer, contradicting ” $v$ undiscovered until now.”

Parent pointers and the BFS tree

The parent[] array isn’t just bookkeeping --- it builds a BFS tree rooted at the source: every reachable vertex $v$ has exactly one parent, namely the vertex from which $v$ was first discovered. The tree’s edges are exactly the ” $v$ first discovered from $u$ ” edges, and the tree’s root-to- $v$ path is a shortest $s \to v$ path in the original graph (length $= \texttt{dist}[v]$ ).

This is the BFS analogue of ch. 9’s parent-pointer trees --- the parent pointers are the data structure BFS produces. Two callers of BFS use it differently:

“Shortest path” callers walk parent pointers backward from the target (path.push_back(prev[v]) in a loop, then std::reverse). $O(\text{path length})$ per query, no extra preprocessing.
“Component” callers ignore the tree and just iterate over dist[] for “everyone reachable from $s$ .”

::: center :::

BFS tree on a 6-vertex undirected graph, source $s$ at the left. Layer $L_0 = \{s\}$ , $L_1 = \{a, b\}$ , $L_2 = \{c, d\}$ , $L_3 = \{e\}$ . Solid arrows are the parent-pointer edges BFS keeps; dotted edges $(a, b)$ and $(c, d)$ are present in the input graph but are not added to the BFS tree because their endpoints were already in the same or adjacent layer when the second endpoint was first discovered.

BFS trace. Run BFS from $s$ on the 6-vertex graph above with adjacency lists $\texttt{adj}[s] = [a, b]$ , $\texttt{adj}[a] = [s, b, c]$ , $\texttt{adj}[b] = [s, a, d]$ , $\texttt{adj}[c] = [a, d, e]$ , $\texttt{adj}[d] = [b, c]$ , $\texttt{adj}[e] = [c]$ .

Step action $\texttt{dist}[s,a,b,c,d,e]$ queue

0 init $0,-,-,-,-,-$ $[s]$ 1 pop $s$ , push $a, b$ $0,1,1,-,-,-$ $[a, b]$ 2 pop $a$ , push $c$ ( $b$ already disc.) $0,1,1,2,-,-$ $[b, c]$ 3 pop $b$ , push $d$ ( $a$ already disc.) $0,1,1,2,2,-$ $[c, d]$ 4 pop $c$ , push $e$ ( $a, d$ already disc.) $0,1,1,2,2,3$ $[d, e]$ 5 pop $d$ (all neighbours discovered) $0,1,1,2,2,3$ $[e]$ 6 pop $e$ (sole neighbour discovered) $0,1,1,2,2,3$ $[\,]$

Final dist array matches the layer assignment from the diagram. Parent pointers track which layer- $d$ vertex first reached each layer- $(d{+}1)$ neighbour. Note step 4: $a$ and $d$ are already discovered so $c$ ‘s edges to them don’t extend the BFS tree --- those become the dotted non-tree edges in the figure.

Typical applications

Shortest path in unweighted graph — unbeatable.
“Friend of a friend” recommendations — explore distance-2 and distance-3 neighborhoods.
Connected components — run BFS from every unvisited vertex; each run finds one component.
Bipartite check — 2-color BFS layers; if an edge connects two same-colored vertices, the graph isn’t bipartite.
Crawling / scraping — explore a website or peer-to-peer network level-by-level.
Closest-of-many search — as in the peer-to-peer example above, find the first node satisfying a condition (fewest hops).

10.6 Depth-First Search

Iterative DFS

void dfs(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<bool> visited(adj.size(), false);
    std::stack<int> s;
    s.push(start);

    while (!s.empty()) {
        int u = s.top(); s.pop();
        if (visited[u]) continue;
        visited[u] = true;
        visit(u);
        for (int v : adj[u])
            if (!visited[v]) s.push(v);
    }
}

Recursive DFS

Shorter and usually what you want:

void dfs(int u, const std::vector<std::vector<int>>& adj,
         std::vector<bool>& visited) {
    if (visited[u]) return;
    visited[u] = true;
    visit(u);
    for (int v : adj[u]) dfs(v, adj, visited);
}

Cost

$O(V + E)$ , same as BFS — each vertex is visited once, each edge examined at most twice (undirected).

BFS vs. DFS: when to pick which

::: center BFS DFS

Auxiliary structure queue (FIFO) stack (LIFO) Shortest path in unweighted graphs yes no Memory (worst case) $O(V)$ queue $O(V)$ stack Explores breadth-first depth-first Natural for distance, levels reachability, ordering Solves shortest path, connectivity topological sort, cycle detection, SCCs :::

Edge classification

DFS isn’t just a way to visit every vertex --- the order in which it visits matters, and that order classifies every edge of the graph into one of four kinds. Each kind has a precise meaning in terms of the DFS tree (the parent-pointer tree DFS produces) and the discovery / finish times $d[u], f[u]$ DFS records when it enters and leaves each vertex. Edge classification is the foundation for cycle detection, topological sort, strongly connected components (§10.14), and articulation-point analysis.

::: center :::

DFS edge classification on a 7-vertex directed graph. DFS roots: $a$ first, then $e$ , then $g$ (each picked when the prior tree finishes). Tree edges (solid black): $a{\to}b$ , $a{\to}c$ , $b{\to}d$ , $e{\to}f$ --- the parent-pointer DFS tree. Back edge (red dashed): $d{\to}a$ closes the cycle $a{\to}b{\to}d{\to}a$ . Forward edge (blue solid): $a{\to}d$ skips ahead to a descendant via a non-tree edge. Cross edge (green dotted): $g{\to}e$ jumps between separately rooted DFS trees and is neither ancestor nor descendant of $g$ .

In an undirected graph, only tree edges and back edges exist --- forward edges and cross edges collapse to back edges under undirected DFS because every non-tree edge is examined twice (once from each endpoint).

Cycle detection on directed graphs

The classification gives a one-line directed-graph cycle test: a directed graph has a cycle if and only if directed-DFS produces a back edge. " $\Leftarrow$ " is the back-edge definition: $(u \to v)$ back edge means $v$ is an ancestor of $u$ , so $v \to \ldots \to u \to v$ is a cycle. " $\Rightarrow$ " is harder: any cycle in $G$ produces a back edge during DFS, because among the cycle’s vertices the one with smallest discovery time $d[\cdot]$ ends up an ancestor of the rest, and the incoming-cycle-edge to that ancestor is a back edge.

In code, you don’t need to maintain $d[\cdot] / f[\cdot]$ explicitly --- a tri-state colour[] array does the job. A vertex is [white]{.smallcaps} (undiscovered), [gray]{.smallcaps} (on the current DFS recursion stack, i.e. “in progress”), or [black]{.smallcaps} (finished). An edge $(u, v)$ to a [gray]{.smallcaps} vertex is a back edge.

enum Colour { WHITE, GRAY, BLACK };

bool hasCycleDFS(int u, const std::vector<std::vector<int>>& adj,
                 std::vector<Colour>& colour) {
    colour[u] = GRAY;
    for (int v : adj[u]) {
        if (colour[v] == GRAY) return true;          // back edge => cycle
        if (colour[v] == WHITE && hasCycleDFS(v, adj, colour))
            return true;
    }
    colour[u] = BLACK;
    return false;
}

bool hasCycle(const std::vector<std::vector<int>>& adj) {
    int n = adj.size();
    std::vector<Colour> colour(n, WHITE);
    for (int u = 0; u < n; ++u)
        if (colour[u] == WHITE && hasCycleDFS(u, adj, colour))
            return true;
    return false;
}

The outer loop over $u$ handles disconnected directed graphs --- any vertex that has not yet been discovered launches a fresh DFS tree. Cost is the same as plain DFS: $O(V + E)$ .

10.7 Directed Graphs

Why DAGs matter

A DAG captures “A must come before B” relationships without contradicting itself. Anything that orders things is a DAG:

Course prerequisites ( $\to$ topological sort).
Build systems ( $\to$ incremental rebuild).
Spreadsheet formulas ( $\to$ evaluation order).
Git commit history ( $\to$ merges and ancestors).
Neural net forward passes.
Dataflow programs.

If your directed graph has a cycle, you have a contradiction: A needs B first, but B also needs A first. Cycle detection on directed graphs is DFS plus a “currently in recursion” flag.

Representation

Same adjacency list or matrix, but only one direction per edge:

// Directed: only add u -> v, not v -> u
adj[u].push_back(v);

Terminology that bites

In-degree of $v$ : number of edges ending at $v$ .
Out-degree of $v$ : number of edges starting at $v$ .
Successor / predecessor: $v$ is a successor of $u$ if $(u \to v) \in E$ ; then $u$ is a predecessor of $v$ .
Source: vertex with in-degree 0 (no one points to it).
Sink: vertex with out-degree 0 (it points to no one).

The build-system DAG, drawn

Every modern build system --- make, Bazel, Cargo, Ninja, cmake –build --- is a topological sort of a dependency DAG with a re-execution rule layered on top. Vertices are build targets; an edge $u \to v$ means ” $v$ depends on $u$ , so $u$ must be built before $v$ .” The topological order is a valid build schedule, and any two vertices that aren’t related by the ancestor relation can be built in parallel. That last sentence is exactly why make -j8 works: independent subtrees of the DAG are independent jobs.

::: center :::

Six-target dependency DAG. A valid topological order is util, cfg, log, core, api, cli --- but cfg, log, util, api, core, cli works equally well. The first three targets share no edges between them, so a parallel build invokes their compilers concurrently; cli sits at the bottom and must wait for both core and api to finish. Add a cycle to this graph (say, cli $\to$ cfg from a stray #include) and no build order exists --- which is exactly the error modern build systems print.

10.8 Weighted Graphs

Why weights complicate things

In an unweighted graph, “shortest” means “fewest hops.” BFS handles it. In a weighted graph, “shortest” means “smallest total weight” — and a path with more edges can easily be shorter than one with fewer:

::: center A $\xrightarrow{10}$ C versus A $\xrightarrow{2}$ B $\xrightarrow{3}$ C (length 10 vs. 5) :::

BFS can’t see this. You need an algorithm that explores in order of weighted distance, not edge count — enter Dijkstra (§10.9).

Representation

// List form: (neighbor, weight) pairs.
std::vector<std::vector<std::pair<int,int>>> adj(V);
adj[u].emplace_back(v, w);

// Matrix form: INT_MAX (or INFINITY) marks "no edge".
std::vector<std::vector<int>> w(V, std::vector<int>(V, INT_MAX));
w[i][i] = 0;
w[u][v] = weight;

Negative weights

Negative edge weights are allowed, but negative cycles break the shortest-path problem entirely: you can loop around the negative cycle forever, driving the total cost to $-\infty$ . Shortest path is undefined.

Relaxation: the universal SSSP primitive

Edge relaxation. Given a weighted edge $(u, v, w)$ and tentative distances $\texttt{dist}[\cdot]$ , the relax operation is

::: center relax $(u, v, w)$ : if $\texttt{dist}[u] + w < \texttt{dist}[v]$ then $\texttt{dist}[v] \gets \texttt{dist}[u] + w$ , $\texttt{prev}[v] \gets u$ . :::

After [relax]{.smallcaps} $(u, v, w)$ , $\texttt{dist}[v] \le \texttt{dist}[u] + w$ holds. The triangle inequality $\texttt{dist}[v] \le \texttt{dist}[u] + w$ for every edge is the shortest-path optimality condition --- once it holds for all edges, $\texttt{dist}[\cdot]$ records true shortest distances.

Relaxation is monotonic: each call either decreases $\texttt{dist}[v]$ or leaves it alone. Every single-source shortest-path algorithm in this chapter --- DAG-relax, Dijkstra, Bellman-Ford --- is just “call [relax]{.smallcaps} on every edge in some order; correctness comes from the order.” The three differ only in order:

DAG-relax (the easy case): topologically sort the DAG, then relax every outgoing edge of each vertex in topological order. One pass; $O(V + E)$ . Correctness: when we process $u$ , any predecessor $p$ on the shortest $s \to v$ path has already been processed (it appears earlier in topological order), so $\texttt{dist}[u]$ is already final, and relaxing $(u, v, w)$ propagates the correct distance to $v$ .
Dijkstra (§10.9): pick the unvisited vertex with smallest tentative distance and relax all its outgoing edges --- a greedy frontier expansion that works because non-negative edges guarantee $\texttt{dist}$ -monotonic processing.
Bellman-Ford (§10.10): relax every edge $|V| - 1$ times. Slower but order-agnostic, so it tolerates negative weights and detects negative cycles.

Once you see the unification, picking the right algorithm collapses to “what’s special about my edge weights / graph structure?“

10.9 Dijkstra’s Shortest Path

Algorithm

For every vertex $v$ , maintain:

dist[v]: best-known shortest distance from the source (initially $\infty$ ).
prev[v]: previous vertex along that best-known path (initially null).

At each step, pull the vertex with smallest tentative dist out of the priority queue (it won’t improve), and relax all its outgoing edges: for each edge $(u, v, w)$ , if dist[u] + w < dist[v], update dist[v] and prev[v].

#include <queue>
#include <vector>
#include <limits>

using Edge = std::pair<int,int>;   // (neighbor, weight)
const int INF = std::numeric_limits<int>::max();

void dijkstra(const std::vector<std::vector<Edge>>& adj, int src,
              std::vector<int>& dist, std::vector<int>& prev) {
    int n = adj.size();
    dist.assign(n, INF);
    prev.assign(n, -1);
    dist[src] = 0;

    // Min-heap of (distance, vertex). std::greater flips the default max-heap.
    using PQE = std::pair<int,int>;
    std::priority_queue<PQE, std::vector<PQE>, std::greater<PQE>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;          // stale entry -- already improved
        for (auto [v, w] : adj[u]) {
            int alt = d + w;
            if (alt < dist[v]) {
                dist[v] = alt;
                prev[v] = u;
                pq.push({alt, v});
            }
        }
    }
}

Why it works – greedy correctness

Negative-edge counterexample, drawn

The cleanest illustration that Dijkstra can break on negative edges is a 3-node graph:

::: center :::

True shortest distances from $s$ : $\texttt{dist}[s] = 0$ , $\texttt{dist}[b] = 3$ , $\texttt{dist}[a] = 0$ (via $s \to b \to a$ at total $3 + (-3) = 0$ ).

What Dijkstra does, however: pop $s$ ( $d = 0$ ), relax both edges so $\texttt{dist}[a] = 1, \texttt{dist}[b] = 3$ . Pop $a$ next (smallest tentative $= 1$ ), declare $\texttt{dist}[a] = 1$ final, finish its empty out-list. Pop $b$ , relax $b \to a$ with weight $-3$ finding $0 < 1$ --- but $a$ is already settled and we never re-expand it. Dijkstra terminates with $\texttt{dist}[a] = 1$ , which is wrong by $1$ .

The greedy-correctness proof above breaks at exactly the line “adds a non-negative edge weight on top of $\texttt{dist}[v]$ .” With a negative edge, a later path can undercut a “finalised” distance. Bellman-Ford (§10.10) survives by relaxing every edge $|V| - 1$ times instead of trusting a greedy ordering.

A worked Dijkstra trace

::: center :::

5-node weighted directed graph. Edge weights are all non-negative, so Dijkstra is the right tool. Source is $s$ .

Dijkstra trace, frame by frame. State at each step is the priority queue (entries $(d, v)$ , smallest-first) and the $\texttt{dist}$ array. The $\infty$ symbol means “not yet relaxed.”

Step action PQ state $\texttt{dist}[s,a,b,c,d]$

0 init $[(0,s)]$ $0, \infty, \infty, \infty, \infty$ 1 pop $(0,s)$ ; relax $s{\to}a$ ( $\infty\!\to\!4$ ), $s{\to}b$ ( $\infty\!\to\!2$ ) $[(2,b),(4,a)]$ $0, 4, 2, \infty, \infty$ 2 pop $(2,b)$ ; relax $b{\to}a$ ( $4\!\to\!3$ ), $b{\to}d$ ( $\infty\!\to\!7$ ) $[(3,a),(4,a)^{*},(7,d)]$ $0, 3, 2, \infty, 7$ 3 pop $(3,a)$ ; relax $a{\to}c$ ( $\infty\!\to\!6$ ) $[(4,a)^{*},(6,c),(7,d)]$ $0, 3, 2, 6, 7$ 4 pop $(4,a)^{*}$ ; stale ( $4 > \texttt{dist}[a] = 3$ ), skip $[(6,c),(7,d)]$ $0, 3, 2, 6, 7$ 5 pop $(6,c)$ ; try $c{\to}d$ : $6{+}2 = 8 \not< 7$ , no-op $[(7,d)]$ $0, 3, 2, 6, 7$ 6 pop $(7,d)$ ; no out-edges $[\,]$ $0, 3, 2, 6, 7$

Entries marked $(\cdot)^{*}$ are stale ones left in the heap by an earlier improvement. Final $\texttt{dist} = [0, 3, 2, 6, 7]$ . Walking $\texttt{prev}[\cdot]$ back recovers each shortest path --- e.g. $d \to b \to s$ at cost $7$ .

Decrease-key vs. lazy-deletion. The textbook Dijkstra calls decrease-key on the priority queue every time a relaxation improves a vertex’s tentative distance. With a binary heap supporting decrease-key the cost is $O((V + E) \log V)$ but the heap implementation needs an index that maps each vertex to its current heap slot --- non-trivial. Standard libraries don’t supply this; you’d reach for boost::heap::fibonacci_heap or roll your own indexed binary heap to get textbook complexity.

The C++ idiom above (the “stale-entry trick”) sidesteps the problem: each relaxation pushes a new smaller entry, leaving the old larger entry in the heap as a tombstone. When a stale entry surfaces at the top we detect it via if (d > dist[u]) continue; and discard. The asymptotic cost is the same $O((V + E) \log V)$ for a binary heap because each edge produces at most one heap push and the heap holds $O(E)$ entries; constants are small and code is short. This is what production C++, competitive programming, and most textbook references actually deploy --- decrease-key is theoretically beautiful, lazy-deletion is what ships.

Cost

::: center Priority-queue implementation Runtime

Unsorted array / linear scan $O(V^2 + E)$ Binary heap (std::priority_queue) $O((V + E) \log V)$ Fibonacci heap $O(E + V \log V)$ :::

For sparse graphs, the binary-heap version is the sweet spot: simple, fast, what you’d reach for in real code. Fibonacci heaps have better theoretical bounds but rarely win in practice because of their hideous constant factors.

Reconstructing the path

After Dijkstra, walk prev backwards from the destination:

std::vector<int> pathTo(int target, const std::vector<int>& prev) {
    std::vector<int> path;
    for (int v = target; v != -1; v = prev[v]) path.push_back(v);
    std::reverse(path.begin(), path.end());
    return path;
}

If prev[target] == -1 and target != src, the target is unreachable.

10.10 Bellman-Ford Shortest Path

Algorithm

struct Edge { int u, v, w; };

bool bellmanFord(int n, const std::vector<Edge>& edges, int src,
                 std::vector<int>& dist, std::vector<int>& prev) {
    dist.assign(n, INF);
    prev.assign(n, -1);
    dist[src] = 0;

    // Main loop: relax every edge V-1 times.
    for (int i = 0; i < n - 1; ++i) {
        for (const auto& e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                prev[e.v] = e.u;
            }
        }
    }

    // Negative-cycle check: one more pass -- if anything still relaxes,
    // the graph has a reachable negative cycle.
    for (const auto& e : edges) {
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
            return false;
    }
    return true;
}

Why V-1 iterations?

A shortest path has at most $V-1$ edges (any more would revisit a vertex, wasting weight if weights are non-negative — and if weights are negative, see below). Each iteration propagates “correct” distances one edge farther along. After $V-1$ passes, every shortest path has been fully propagated, as long as no negative cycles exist.

If an edge is still relaxable on a $V$ -th iteration, then some path keeps getting shorter — a negative cycle is the only way that can happen.

$|V|-1$ -round correctness, by induction on path length. Let $\delta_k(v)$ denote the length of the shortest $s \to v$ path using at most $k$ edges. We show after the $k$ -th outer iteration $\texttt{dist}[v] \le \delta_k(v)$ for every $v$ .

Base ( $k = 0$ ): only $s$ has a $0$ -edge path, with cost $0$ ; the initialisation $\texttt{dist}[s] = 0, \texttt{dist}[v] = \infty$ matches.

Step ( $k \to k{+}1$ ): a $(k{+}1)$ -edge path to $v$ is some $k$ -edge path to a predecessor $p$ followed by edge $(p, v, w)$ . By IH $\texttt{dist}[p] \le \delta_k(p)$ after iteration $k$ . The $(k{+}1)$ -th iteration relaxes every edge, including $(p, v, w)$ , so afterwards $\texttt\{dist\}[v] \le \texttt\{dist\}[p] + w \le \delta_k(p) + w = \delta_\{k+1\}(v)$ (taking $p$ that achieves the minimum).

If the graph has no negative cycle, every shortest $s \to v$ path is simple and uses at most $|V| - 1$ edges, so $\delta_{|V|-1}(v) = \delta(v)$ (the true shortest-path cost). Thus $|V| - 1$ iterations are enough.

If there is a reachable negative cycle, there is some edge $(u, v, w)$ on the cycle with $\texttt{dist}[u] + w < \texttt{dist}[v]$ no matter how many rounds we run; the $|V|$ -th relaxation pass would still improve it. That’s the negative-cycle test: after $|V| - 1$ rounds, do one more --- any further relaxation $\Rightarrow$ negative cycle reachable from $s$ .

Cost

$O(VE)$ . Roughly $V$ times slower than Dijkstra in the worst case, but:

Handles negative weights.
Detects negative cycles.
Works on any graph representation — just give it a list of edges.
Easy to parallelize (independent edge relaxations).

Dijkstra vs. Bellman-Ford, decision flowchart

::: center Situation Use

All edges non-negative, sparse Dijkstra + binary heap
Negative edges, no negative cycles Bellman-Ford
Need to detect negative cycles Bellman-Ford
All-pairs shortest paths Floyd-Warshall (§10.13)
Unweighted graph BFS (not either of these)
:::

Bellman-Ford trace, with negative-cycle case. Edge list $E = [(s, a, 4), (s, b, 5), (a, c, -3), (b, c, 1), (c, b, -2)]$ on 4 vertices $\{s, a, b, c\}$ , source $s$ . Walk the relaxations in the listed edge order each pass; show $\texttt{dist}$ after each full pass.

Pass relaxations $\texttt{dist}[s, a, b, c]$

0 init $0, \infty, \infty, \infty$ 1 $s{\to}a$ ( $\infty\!\to\!4$ ), $s{\to}b$ ( $\infty\!\to\!5$ ), $a{\to}c$ ( $\infty\!\to\!1$ ), $c{\to}b$ ( $5\!\to\!-1$ ). $0, 4, -1, 1$ 2 $b{\to}c$ ( $1\!\to\!0$ ), $c{\to}b$ ( $-1\!\to\!-2$ ). $0, 4, -2, 0$ 3 $b{\to}c$ ( $0\!\to\!-1$ ), $c{\to}b$ ( $-2\!\to\!-3$ ). $0, 4, -3, -1$ $|V|{-}1 = 3$ rounds done, but …
4 $b{\to}c$ relaxes $-3 + 1 = -2 < -1$ $\Rightarrow$ negative cycle. ---

The cycle is $b \to c \to b$ with weight $1 + (-2) = -1 < 0$ , so each pass over $\{b, c\}$ shaves another $-1$ off both distances indefinitely. Bellman-Ford’s $|V|$ -th-round test catches it --- the algorithm returns false and the caller knows shortest paths from $s$ to $\{b, c\}$ are undefined.

If we delete the $c \to b$ edge (no negative cycle, just one negative edge $a \to c$ with weight $-3$ ), Bellman-Ford converges to $\texttt{dist} = [0, 4, 5, 1]$ after one full pass and the $|V|$ -th-round test reports no further relaxation. Negative edges alone are fine; negative cycles reachable from the source are not.

10.11 Topological Sort

Kahn’s algorithm (in-degree method)

Repeatedly peel off vertices with no incoming edges — they’re safe to do first.

std::vector<int> topoSortKahn(int n,
                              const std::vector<std::vector<int>>& adj) {
    std::vector<int> indeg(n, 0);
    for (int u = 0; u < n; ++u)
        for (int v : adj[u]) ++indeg[v];

    std::queue<int> q;
    for (int u = 0; u < n; ++u)
        if (indeg[u] == 0) q.push(u);

    std::vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);
    }

    if ((int)order.size() != n) return {};  // cycle detected
    return order;
}

If the final order doesn’t have all $n$ vertices, the remaining vertices form a cycle — automatic cycle detection, no extra work.

DFS-based topological sort

Alternative: DFS, and push each vertex onto a result stack when it finishes (after its recursion returns). Reverse the stack.

void dfsTopo(int u, const std::vector<std::vector<int>>& adj,
             std::vector<bool>& visited, std::vector<int>& out) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v]) dfsTopo(v, adj, visited, out);
    out.push_back(u);   // post-order: u is "done" now
}

std::vector<int> topoSortDfs(int n,
                             const std::vector<std::vector<int>>& adj) {
    std::vector<bool> visited(n, false);
    std::vector<int> out;
    for (int u = 0; u < n; ++u)
        if (!visited[u]) dfsTopo(u, adj, visited, out);
    std::reverse(out.begin(), out.end());
    return out;
}

Why the reversal? DFS finishes deeper-in-the-dependency-chain vertices first. In a topological ordering, those should come last (they depend on earlier stuff). Reversing puts them in the right order.

Cost

Both are $O(V + E)$ .

Kahn vs. DFS

Kahn is iterative and natural for streaming/parallel processing — multiple vertices can be in the “ready” queue simultaneously.
DFS is shorter to write and fits naturally with other DFS-based algorithms (SCC, cycle detection).

Pick based on context. Most textbooks teach DFS; most real-world schedulers (like Tarjan’s, or make’s job dispatcher) use Kahn-style because they can work on “what’s ready now” incrementally.

10.12 Minimum Spanning Tree

Kruskal’s algorithm (greedy edges)

Sort all edges by weight. Add each edge to the MST unless it would create a cycle. Stop when you have $V-1$ edges.

“Would it create a cycle?” is answered with a union-find (disjoint-set) data structure: two vertices are in the same component iff their roots are equal.

struct DSU {
    std::vector<int> parent, rank_;
    DSU(int n) : parent(n), rank_(n, 0) {
        std::iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];   // path compression
            x = parent[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) std::swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b]) ++rank_[a];
        return true;
    }
};

struct Edge { int u, v, w; };

std::vector<Edge> kruskal(int n, std::vector<Edge> edges) {
    std::sort(edges.begin(), edges.end(),
              [](const Edge& a, const Edge& b){ return a.w < b.w; });

    DSU dsu(n);
    std::vector<Edge> mst;
    for (const auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            mst.push_back(e);
            if ((int)mst.size() == n - 1) break;
        }
    }
    return mst;
}

Cost

$O(E \log E) = O(E \log V)$ (since $E \leq V^2$ , the two are equivalent up to a constant factor). Dominated by the sort; union-find operations are near- $O(1)$ amortized.

Why the greedy works

Cut property. A cut of a connected undirected graph $G = (V, E)$ is a partition $V = S \sqcup (V \setminus S)$ with $S \neq \emptyset, V$ . An edge $(u, v)$ crosses the cut if $u \in S$ and $v \in V \setminus S$ (or vice versa). The cut property says: for any cut whose crossing edges have a unique minimum-weight edge $e^* = (u^*, v^*, w^*)$ , every MST of $G$ contains $e^*$ . (With ties, $e^*$ is in some MST.)

Sketched proof (exchange argument). Take any MST $T$ . If $T$ contains $e^*$ , done. Otherwise $T \cup \{e^*\}$ has a cycle $C$ that uses $e^*$ plus other edges; $C$ must cross the cut an even number of times, so $C$ contains another crossing edge $e' = (u', v', w')$ with $w' > w^*$ . Then $T' = T \cup \{e^*\} \setminus \{e'\}$ is a spanning tree with total weight $w(T) - w' + w^* < w(T)$ , contradicting $T$ being minimum. So $e^* \in T$ after all. (CLRS Theorem 23.1.)

These two lemmas justify both Kruskal and Prim:

Kruskal. Each unite-accepting edge is the minimum-weight edge across the cut $(S, V \setminus S)$ where $S$ is the connected component of $u$ in the partial MST. So by the cut property the edge is safe to take.
Prim. Each “cheapest edge from the inside set to an outside vertex” is the minimum-weight edge across the cut $(\text{inside}, \text{outside})$ . Same cut property, different cut.

The cycle property is the anti-MST companion: it tells you which edges to never bother with --- whenever a cycle’s heaviest edge can be replaced by a lighter cycle alternative, the heavy edge is dead weight.

Prim’s algorithm (greedy vertex frontier)

Alternative MST algorithm: start from any vertex, repeatedly add the cheapest edge that connects an “inside” vertex to an “outside” vertex. Structurally it’s Dijkstra with a different relaxation rule --- compare edge weight directly, not cumulative distance. The min-heap holds (edge weight, outside vertex, inside parent) tuples; we pop the cheapest crossing edge, add the outside vertex to the inside set, and push the newly-uncovered edges.

struct PrimEdge { int w, v, parent; };
struct PrimCmp {
    bool operator()(const PrimEdge& a, const PrimEdge& b) const {
        return a.w > b.w;   // min-heap on weight
    }
};

// adj[u] = vector of (neighbour, weight) pairs.
std::vector<Edge> prim(int n,
                       const std::vector<std::vector<std::pair<int,int>>>& adj) {
    std::vector<bool> inMST(n, false);
    std::priority_queue<PrimEdge, std::vector<PrimEdge>, PrimCmp> pq;
    pq.push({0, 0, -1});                          // start at vertex 0

    std::vector<Edge> mst;
    while (!pq.empty() && (int)mst.size() < n - 1) {
        auto [w, v, parent] = pq.top(); pq.pop();
        if (inMST[v]) continue;                   // stale entry, skip
        inMST[v] = true;
        if (parent != -1)
            mst.push_back({parent, v, w});
        for (auto [nbr, weight] : adj[v])
            if (!inMST[nbr])
                pq.push({weight, nbr, v});
    }
    return mst;                                   // empty if graph disconnected
}

The same stale-entry / lazy-deletion idiom from §10.9 Dijkstra applies: we push duplicates instead of decrease-key, and filter by inMST[v] on pop. With a binary heap the cost is $O((V + E) \log V)$ . With an array-based priority queue and $O(V)$ extract-min the cost is $O(V^2)$ --- and on a dense graph ( $E = \Theta(V^2)$ ) array-Prim’s $O(V^2)$ beats Kruskal’s $O(E \log E) = O(V^2 \log V)$ because we skip the sort and the union-find both. Production graph libraries pick by density.

::: center :::

6-vertex weighted graph and its MST. Heavy tan edges form the MST (total weight $1{+}2{+}3{+}4{+}2 = 12$ ), thin grey edges are the non-MST edges $(b,e,6), (e,f,8), (a,c,7)$ . Cut-property sanity check on the cut $S = \{a\}, V \setminus S = \{b, c, d, e, f\}$ : crossing edges are $(a,b,1), (a,d,3), (a,c,7)$ , with min $(a,b,1)$ --- which is in the MST. By the cycle property, the cycle $a{-}b{-}c{-}a$ (weights $1, 2, 7$ ) has heaviest edge $(a,c,7)$ , which is correctly excluded.

DSU’s amortised cost: $O(\alpha(n))$ via inverse Ackermann. The Kruskal DSU above implements both path compression (parent[x] = parent[parent[x]] as we walk up) and union-by-rank (lower-rank tree gets reattached under the higher-rank one). With both, a sequence of $m$ find + unite operations costs $O(m \cdot \alpha(n))$ amortised, where $\alpha(\cdot)$ is the inverse Ackermann function. For $n \le 2^{2^{2^{16}}}$ (astronomically more atoms than the observable universe contains), $\alpha(n) \le 4$ , so each operation is effectively $O(1)$ in any realistic setting.

The proof is genuinely hard --- Tarjan’s 1975 paper introduced the amortised-analysis framework that ch. 9 §9.9 augmentation-cost arguments use. CLRS Ch 21 carries the full derivation. For us, the operative fact is: $\alpha(n)$ never exceeds $4$ in practice, so Kruskal’s runtime in the wild is dominated by the $O(E \log E)$ sort, not the union-find.

::: center Kruskal Prim

Approach greedy on edges greedy on vertex frontier Needs sorted edge list, union-find adjacency list, priority queue Cost $O(E \log E)$ $O(E \log V)$ w/ binary heap Good when edges are easy to enumerate graph is dense, adjacency is fast :::

10.13 All-Pairs Shortest Path (Floyd-Warshall)

Algorithm

Maintain dist[i][j] = current best-known distance from $i$ to $j$ . Initialize:

dist[i][i] = 0.
dist[i][j] = w(i,j) if the edge exists.
dist[i][j] = $\infty$ otherwise.

Then iterate: for each intermediate vertex $k$ , for each pair $(i, j)$ , ask “does going through $k$ beat the current best?”

void floydWarshall(std::vector<std::vector<int>>& dist) {
    int n = dist.size();
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (dist[i][k] != INF && dist[k][j] != INF
                    && dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
}

Why it works – the k-loop invariant

Cost

$O(V^3)$ time, $O(V^2)$ space. That’s cubic, but with tiny constants — three nested for loops of integer additions. On modern hardware it’s vectorizable and absolutely flies for $V$ up to a few thousand.

Floyd-Warshall vs. running Dijkstra V times

::: center Dijkstra from every source Floyd-Warshall

Total cost (binary heap) $O(V (V+E) \log V)$ $O(V^3)$ Handles negative edges? no yes Detects negative cycles? no yes (check diagonal) Code complexity moderate very simple Ideal on sparse, non-negative dense, or need negative-weight support :::

Path reconstruction

Floyd-Warshall only computes distances. To recover paths, track the intermediate vertex alongside:

std::vector<std::vector<int>> next;   // next[i][j] = first hop from i toward j

// During init: next[i][j] = j if edge exists, else -1; next[i][i] = i.
// During update:
if (dist[i][k] + dist[k][j] < dist[i][j]) {
    dist[i][j] = dist[i][k] + dist[k][j];
    next[i][j] = next[i][k];
}

// Reconstruct path i -> j:
std::vector<int> path = {i};
while (path.back() != j) path.push_back(next[path.back()][j]);

Algebraic view

Floyd-Warshall is min-plus matrix multiplication in disguise. Replace “product + sum” with “sum + min,” and the adjacency matrix raised to high enough a power (in this semiring) is exactly the all-pairs-shortest-path matrix. This connects shortest paths to a whole field of tropical algebra, used in everything from compiler optimization to network calculus.

10.14 Strongly Connected Components

Kosaraju’s algorithm (DFS twice)

The trick is to combine §10.6’s DFS finish-time ordering with the transpose graph $G^T$ (every edge reversed). Two passes:

Run DFS on $G$ and push vertices to a stack in finish-time order (the latest-finishing vertex on top).
Pop vertices off the stack one at a time. Each pop runs a fresh DFS in $G^T$ starting at the popped vertex, restricted to so-far-unvisited vertices. The set of vertices each restricted DFS reaches is one SCC.

Why it works: the latest-finishing vertex of pass 1 is in a “source SCC” of the SCC-DAG (no incoming inter-SCC edges). DFS from that vertex in $G^T$ reverses the inter-SCC edges, so it cannot escape its own SCC --- giving exactly the SCC’s vertex set. Removing those, the next latest-finishing unvisited vertex is in the next source SCC of the remaining DAG, and so on. CLRS Theorem 22.16 carries the proof.

// Pass 1: DFS on G, pushing vertices in finish-time order.
void dfsForward(int u, const std::vector<std::vector<int>>& adj,
                std::vector<bool>& visited, std::vector<int>& order) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v]) dfsForward(v, adj, visited, order);
    order.push_back(u);   // post-order: latest finishes go on the back
}

// Pass 2: DFS on G^T, collecting one SCC per call.
void dfsBackward(int u, const std::vector<std::vector<int>>& adjT,
                 std::vector<bool>& assigned, std::vector<int>& comp) {
    assigned[u] = true;
    comp.push_back(u);
    for (int v : adjT[u])
        if (!assigned[v]) dfsBackward(v, adjT, assigned, comp);
}

std::vector<std::vector<int>> kosaraju(
        int n, const std::vector<std::vector<int>>& adj) {
    // Build transpose G^T.
    std::vector<std::vector<int>> adjT(n);
    for (int u = 0; u < n; ++u)
        for (int v : adj[u]) adjT[v].push_back(u);

    // Pass 1.
    std::vector<bool> visited(n, false);
    std::vector<int> order;
    for (int u = 0; u < n; ++u)
        if (!visited[u]) dfsForward(u, adj, visited, order);

    // Pass 2: pop vertices in reverse finish order, DFS on G^T.
    std::vector<bool> assigned(n, false);
    std::vector<std::vector<int>> sccs;
    for (int i = (int)order.size() - 1; i >= 0; --i) {
        int u = order[i];
        if (!assigned[u]) {
            std::vector<int> comp;
            dfsBackward(u, adjT, assigned, comp);
            sccs.push_back(std::move(comp));
        }
    }
    return sccs;
}

Cost is $O(V + E)$ : two linear-time DFS traversals plus one transpose construction. Output sccs is a list of vertex sets, one per SCC, emitted in topological order on the SCC-DAG (the first SCC popped is a source).

Tarjan’s algorithm computes SCCs in a single DFS pass using two augmentations per vertex --- disc[u] (discovery time) and low[u] (smallest disc reachable via tree edges plus at most one back edge from $u$ ‘s subtree). When DFS finishes a vertex $u$ with $\texttt{disc[u]} = \texttt{low[u]}$ , $u$ is the root of its SCC, and that SCC is exactly the contiguous span of an explicit DFS stack popped down to $u$ . Same $O(V + E)$ asymptotic cost, half the constant factor (no transpose to build), but the correctness argument is more delicate. Use Tarjan when constant factors matter or you can’t afford the $O(E)$ transpose memory; use Kosaraju when clarity wins. CLRS §22.5 has Kosaraju; the Tarjan derivation lives in CLRS exercises and Sedgewick §4.2.

::: center Three SCCs in this 6-vertex digraph. $\{a, b\}$ via the $a \leftrightarrow b$ pair; $\{c, d, e\}$ via the cycle $c \to d \to e \to c$ ; $\{f\}$ singleton. Inter-SCC edges $b \to c$ and $d \to f$ collapse to a 3-vertex condensation DAG $\{a,b\} \to \{c,d,e\} \to \{f\}$ . :::

Applications

SCCs are the workhorse for two production-relevant problems:

2-SAT solving in linear time. Encode a 2-SAT formula $\bigwedge_i (\ell_i \vee \ell'_i)$ as the implication graph on $2n$ literals: each clause $(\ell \vee \ell')$ contributes two edges, $\neg \ell \to \ell'$ and $\neg \ell' \to \ell$ . The formula is satisfiable iff no variable $x$ has $x$ and $\neg x$ in the same SCC --- and a satisfying assignment is recovered from the SCC topological order. Total cost $O(n + m)$ . Compare 3-SAT, which is NP-complete --- the SCC decomposition is what makes 2-SAT tractable.
Dependency-cycle detection in package managers. cargo, npm, pip all need to detect when a set of packages forms a mutual-dependency cycle (which prevents a clean install order). SCC computation surfaces every such cycle as a non-singleton SCC; the package manager either errors out or treats the SCC as a single “compile-everyone- together” unit, depending on the language’s circular- import rules.

10.15 Picking the right algorithm: master decision table

By now you’ve seen seven (sometimes eight) graph algorithms with overlapping use-cases. The right tool depends on which problem (single-pair / single-source / all-pairs / MST / topological / cycle-detect / SCC / connectivity) and which graph properties (unweighted / non-negative / negative-no-cycle / negative-with-cycle / DAG / sparse / dense). The following master chooser collapses every chapter algorithm into one place. Cell entries name the algorithm, complexity, and chapter section.

::: center :::

The columns also encode the sparse vs. dense dimension: sparse $\Rightarrow$ favour adjacency-list-based algorithms (Dijkstra heap form, Bellman-Ford, Kruskal); dense $\Rightarrow$ favour matrix-based or array-PQ algorithms (Floyd-Warshall, Prim-with-array-PQ). The chapter map and the mastery checklist both forward-ref this table; if you internalise just one artefact from the chapter, this is the one.

10.16 Forward direction: A*, Johnson, network flow, planarity

ch. 10 covers the canonical undergraduate graph toolkit. The following are the algorithms a senior-level / graduate course would build on top --- not implemented here, but pointed at so the curious reader knows what to look for.

A^*^. Dijkstra plus an admissible heuristic $h(v)$ that lower-bounds the true distance from $v$ to the goal. Replace the priority key $\texttt{dist}[v]$ with $\texttt{dist}[v] + h(v)$ ; the priority queue now expands “most-promising” vertices first instead of just nearest. Admissibility ( $h$ never overestimates) preserves optimality; consistency ( $h(u) \le w(u,v) + h(v)$ ) preserves the “finished-once-popped” invariant and avoids re-expansion. A* is the workhorse of game-AI pathfinding (grid heuristics like Manhattan / Euclidean distance), robot motion planning, and the SAT-solver AI literature. CLRS §24.5 sketches it; Russell & Norvig’s Artificial Intelligence: A Modern Approach (Pearson) carries the full treatment.

Johnson’s algorithm. All-pairs shortest paths on sparse graphs with possibly negative edges:

Add a virtual source $s$ with zero-weight edges to every vertex.
Run Bellman-Ford from $s$ to compute potentials $h(v) = \delta(s, v)$ ( $O(VE)$ ).
Reweight every edge: $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ . The reweighted graph has non-negative edges and preserves shortest paths.
Run Dijkstra from every vertex on the reweighted graph ( $V$ runs $\times$ $O((V{+}E)\log V)$ ).

Total $O(VE + V(V+E)\log V)$ , beating Floyd-Warshall’s $O(V^3)$ when $E \ll V^2$ . CLRS §25.3.

Network flow (Ford-Fulkerson, Edmonds-Karp). Compute the maximum flow on a directed graph with edge capacities. Both algorithms repeatedly find an augmenting path from source to sink with residual capacity and push flow along it. Ford-Fulkerson works with any path-finding (potentially exponential on weird inputs); Edmonds-Karp insists on shortest augmenting paths via BFS, giving $O(VE^2)$ provably. Network flow underpins bipartite matching, project-selection, image segmentation, and a quarter of the algorithms in operations research. CLRS Ch 26 covers Ford-Fulkerson + Edmonds-Karp; later material (push-relabel, Dinic’s) lives in graduate texts.

Planar graphs. A graph is planar if it can be drawn in the plane with no edge crossings. The 4-colour theorem says every planar graph’s vertices can be coloured with at most 4 colours such that no edge connects same-coloured vertices --- a result so notorious it’s the only major mathematical theorem proved by computer assistance (Appel & Haken, 1976). Linear-time planarity testing exists (Hopcroft & Tarjan 1974) but the algorithm is intricate; you’d reach for a library (boost::graph::boyer_myrvold_planarity_test) rather than re-implement.

Chapter takeaway. Graphs are the universal data structure of computer science. Every major algorithm in this chapter --- BFS, DFS, Dijkstra, Bellman-Ford, topological sort, Kruskal, Prim, Floyd-Warshall, Kosaraju --- is an instance of “explore the graph by expanding a frontier in some specific order.” The frontier type (queue, stack, priority queue, edge-sorted list, triple loop, two-pass DFS) and the relaxation rule (visit once, update-if-shorter, take cheapest crossing edge, …) are what distinguish them. Internalize the pattern and you can reason about a new graph algorithm in minutes.

Looking ahead. Chapter 11 introduces B-trees as the shallow-and-wide alternative for disk-based or cache-friendly storage --- the parent-pointer pattern carries straight over, just with a fan-out of $B$ pointers per node so $h = O(\log_B n)$ on a disk-page geometry. Filesystems and database indices use B-trees exactly because the disk-block layout is a graph problem (block references = directed edges) where the substrate cost dominates the algorithmic cost. Chapter 12 covers the set ADT in full; the visited / discovered sets that BFS and DFS rely on, the inMST flag in Prim, the assigned flag in Kosaraju --- all are “does the set contain $x$ ?” / “add $x$ to the set” workloads the set ADT formalises. Forward direction beyond cs-300 is in §10.16: A*, Johnson’s, network flow, and planar graphs are the next-grade-up algorithms that build on the toolkit you have here.