Two ways to store a graph and two ways to walk it — and almost every graph algorithm in the rest of the book is one of those walks with bookkeeping attached.
Part VI opens with the foundations: how to represent a graph, and the two systematic traversals. Breadth-first search explores by distance and yields shortest paths in unweighted graphs. Depth-first search explores by following edges as far as possible, and its timestamp structure yields topological sort and strongly connected components almost for free. If you know BFS and DFS cold, the rest of Part VI is variations.
A graph G = (V, E) has two standard representations, and the choice matters.
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Structure | Array of |V| lists; Adj[u] holds the neighbours of u | |V| × |V| matrix with aᵢⱼ = 1 if (i,j) ∈ E |
| Space | Θ(V + E) | Θ(V²) |
Test if (u,v) ∈ E | O(degree(u)) | Θ(1) |
Enumerate neighbours of u | Θ(degree(u)) | Θ(V) |
| Preferred for | Sparse graphs, |E| ≪ |V|² — the usual case | Dense graphs, or when you need O(1) edge tests |
O(V + E) rather than O(V²). For weighted graphs, store the weight alongside each neighbour in the list, or in the matrix entry.A note on notation used throughout: inside asymptotic bounds CLRS writes V and E for |V| and |E|. So O(V + E) means O(|V| + |E|).
Given a source s, BFS explores the graph in order of increasing distance, discovering all vertices at distance k before any at distance k+1.
Each vertex has a colour recording its state: white (undiscovered), grey (discovered, neighbours not yet all explored), black (finished).
BFS(G, s)
1 for each vertex u ∈ G.V - {s}
2 u.color = WHITE; u.d = ∞; u.π = NIL
3 s.color = GREY; s.d = 0; s.π = NIL
4 Q = ∅
5 ENQUEUE(Q, s)
6 while Q ≠ ∅
7 u = DEQUEUE(Q)
8 for each v ∈ G.Adj[u]
9 if v.color == WHITE // first time we have seen v
10 v.color = GREY
11 v.d = u.d + 1
12 v.π = u
13 ENQUEUE(Q, v)
14 u.color = BLACKO(V + E). Each vertex is enqueued at most once, and each adjacency list is scanned once.
v.d = δ(s, v) for every vertex v, where δ is the shortest-path distance measured in number of edges. Moreover the predecessor pointers π form a breadth-first tree in which the unique path from s to v is a shortest path.Two supporting facts:
(u,v), δ(s,v) ≤ δ(s,u) + 1. One edge cannot shorten a distance by more than one.d values differ by at most 1, and they are in non-decreasing order. This is the invariant that keeps the search level by level.DFS goes as deep as possible before backtracking, and unlike BFS it searches from every vertex, producing a depth-first forest rather than a single tree.
DFS(G) DFS-VISIT(G, u)
1 for each u ∈ G.V 1 time = time + 1
2 u.color = WHITE 2 u.d = time // discovered
3 u.π = NIL 3 u.color = GREY
4 time = 0 4 for each v ∈ G.Adj[u]
5 for each u ∈ G.V 5 if v.color == WHITE
6 if u.color == WHITE 6 v.π = u
7 DFS-VISIT(G, u) 7 DFS-VISIT(G, v)
8 u.color = BLACK
9 time = time + 1
10 u.f = time // finishedΘ(V + E). Every vertex gets two timestamps: u.d when first discovered (turns grey) and u.f when its adjacency list is exhausted (turns black). Timestamps run from 1 to 2|V|.
The timestamps are not incidental — they carry the structure that the next two algorithms exploit.
u and v, exactly one of the following holds: the intervals [u.d, u.f] and [v.d, v.f] are entirely disjoint, and neither is a descendant of the other; or one interval is entirely contained in the other, and the inner vertex is a descendant of the outer.Write out the discovery and finish times as a sequence of parentheses and they nest properly, exactly like well-formed brackets. Partial overlap never happens.
v is a descendant of u in the depth-first forest if and only if, at the time u.d when the search discovers u, there is a path from u to v consisting entirely of white vertices.DFS classifies every edge (u,v) by the colour of v when the edge is first explored.
| Type | v is | Meaning |
|---|---|---|
| Tree edge | WHITE | v was discovered by this edge; it is in the DFS forest. |
| Back edge | GREY | v is an ancestor of u. Indicates a cycle. |
| Forward edge | BLACK, u.d < v.d | v is a descendant, reached earlier by another route. |
| Cross edge | BLACK, u.d > v.d | Everything else — between subtrees or between trees. |
A topological sort of a directed acyclic graph is a linear ordering of the vertices such that every edge (u,v) has u before v. This is the “do the prerequisites first” ordering: build dependencies, course prerequisites, task scheduling, spreadsheet recalculation.
TOPOLOGICAL-SORT(G)
1 call DFS(G) to compute finish times v.f for each vertex v
2 as each vertex is finished, insert it onto the front of a linked list
3 return the linked list of verticesΘ(V + E). That is the entire algorithm: DFS, and output in decreasing order of finish time.
Why it works (Theorem 20.12). For any edge (u,v) in a DAG, DFS gives v.f < u.f. If v is white when (u,v) is explored it becomes a descendant and finishes first; if it is black it already finished; and it cannot be grey, since that would make (u,v) a back edge and the graph would have a cycle. So sorting by decreasing finish time puts every u before every v.
Θ(V+E), easier to implement iteratively, and it detects cycles naturally by leaving vertices behind. CLRS gives the DFS version because it reuses machinery already built.u, v in it has a path from u to v and a path from v to u. Contracting each SCC to a single vertex yields the component graph, which is always a DAG.The algorithm is startlingly short given what it computes.
STRONGLY-CONNECTED-COMPONENTS(G)
1 call DFS(G) to compute finish times u.f for each vertex u
2 compute Gᵀ, the transpose of G (all edges reversed)
3 call DFS(Gᵀ), but in the main loop consider vertices in order
of decreasing u.f as computed in line 1
4 output the vertices of each tree in the depth-first forest
of line 3 as a separate strongly connected componentΘ(V + E) — two depth-first searches and one transpose. This is Kosaraju’s algorithm.
G and Gᵀ have exactly the same strongly connected components, since mutual reachability is symmetric under edge reversal. Processing Gᵀ in decreasing finish order visits the components in topological order of the component DAG, and in the transposed graph the edges between components point the wrong way — so each DFS tree cannot escape its own component. That containment is what makes each tree exactly one SCC.Θ(V+E) space and are the default for sparse graphs; adjacency matrices use Θ(V²) and give O(1) edge tests.O(V+E), and computes shortest paths by edge count plus a breadth-first tree.Θ(V+E), searches from every vertex, and records d and f timestamps.v is a descendant of u iff an all-white path existed at time u.d.Θ(V+E), DAGs only.G, then DFS on Gᵀ in decreasing finish order. Each resulting tree is one component. Θ(V+E).Chapter 21 adds weights and asks for a minimum spanning tree: the cheapest set of edges connecting every vertex. Both standard algorithms, Kruskal’s and Prim’s, are greedy, and both are instances of one generic method justified by a single theorem about safe edges.