Further Reading: Graph Representations, Traversal, and Search

Annotated pointers for going deeper. Start with the textbook sections that re-cover BFS, DFS, and representations at your pace, then branch toward whichever pull is strongest: the algorithmics (CLRS), the CS-flavored proofs (MIT 6.042), or the graph theory behind it (West).

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §10.1–10.5 The market-standard discrete-math treatment of graph representations (adjacency matrices and lists), connectivity, and graph isomorphism, with a large, well-graded exercise bank. If you want more drill on representations and the matrix/list tradeoff than this chapter provides, start here.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042J), the graph chapters Freely available. The most CS-flavored presentation in print: graphs are developed alongside the proof techniques we lean on, so the connectivity and tree arguments read as continuations of induction rather than a separate world. Excellent companion for the §28.2 distance proof and the spanning-tree facts of §28.4.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the graph theory chapter Freely available. A gentle, example-first treatment of graphs, trees, and traversal. A good first re-read if the formal definitions in §28.1 felt dense; its tree material pairs well with §28.4.

The algorithmics of BFS, DFS, and beyond

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), Chapter 20 ("Elementary Graph Algorithms") The canonical algorithmic reference for everything in this chapter: adjacency-list/matrix tradeoffs, BFS with its shortest-path proof, DFS with the full white/gray/black edge-classification machinery we only gesture at in §28.3–28.5, topological sort, and the $\Theta(V+E)$ analysis. Read this next if you want the rigorous, complete version of §28.5's finishing-time argument and directed cycle detection. The Deep Dive path in this chapter points here.

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), §2.1 (loop invariants) The §28.2 proof that BFS computes shortest distances is a loop-invariant argument; this section is the canonical reference for the initialization/maintenance/termination pattern it uses (the same one from Chapter 6).

Knuth, The Art of Computer Programming, Vol. 1 (3rd ed.), §2.2.3 and §2.3 Knuth's treatment of linked structures and trees — the data-structure substratum beneath adjacency lists and the traversal trees of §28.4. Denser and more machine-oriented; for readers who want to see the representations at the level of memory and pointers.

The graph theory behind the algorithms

West, Introduction to Graph Theory (2nd ed.), Chapters 1–2 The mathematician's view: paths, connection, trees, and spanning trees developed as theory rather than as code. Read this if you want the structural results — why a connected graph on $n$ vertices has a spanning tree with exactly $n-1$ edges (§28.4) — proved in full generality, and as background for the spanning-tree material returning in Chapter 32.

Rosen, Discrete Mathematics and Its Applications (8th ed.), §11.4–11.5 (spanning trees) A discrete-math-level treatment of spanning trees and tree traversal that expands the §28.4 "intro" into a full section, including BFS and DFS spanning trees explicitly. A natural bridge to Chapter 32's minimum-spanning-tree algorithms.

Suggested order

  1. Re-read §§28.1–28.6 here, then do Rosen §§10.1–10.4 exercises for drill on representations and connectivity.
  2. Read the MIT 6.042 graph chapters for the CS-flavored framing of connectivity and trees.
  3. Read CLRS Chapter 20 in full — it is the single best deepening of this chapter, and it completes the edge-classification and directed-cycle machinery that §28.3–28.5 only sketch.
  4. If the BFS shortest-path proof still feels shaky, reread CLRS §2.1 on loop invariants alongside Chapter 6.
  5. For the underlying theory (spanning trees, connectivity proofs), read West Chapters 1–2 — and keep it handy for Chapter 32.