Chapter 28 — Key Takeaways

Graph Representations, Traversal, and Search (BFS & DFS). Reread this before an exam.

Two representations

	Adjacency matrix	Adjacency list
What it is	$n\times n$ table $A$; $A[i][j]=1$ iff edge $\{i,j\}$ (or arc $(i,j)$)	dict/array: each vertex $\mapsto$ list of neighbors
Space	$\Theta(n^2)$	$\Theta(n+m)$
Edge test "$\{i,j\}$?"	$\Theta(1)$	$\Theta(\deg i)$
List neighbors of $v$	$\Theta(n)$	$\Theta(\deg v)$
Iterate all edges	$\Theta(n^2)$	$\Theta(n+m)$
Undirected $\Rightarrow$	symmetric matrix; $\deg(i)=$ row sum	each edge stored twice (once per endpoint)
Use when	dense ($m\approx n^2$), edge-test-heavy, linear algebra ($A^k$ counts walks)	sparse ($m\ll n^2$), traversal-heavy — the default

Notation: $n=\lvert V\rvert$ vertices, $m=\lvert E\rvert$ edges; inside Big-O written $V$, $E$.

	BFS	DFS
Data structure	FIFO queue	LIFO stack / recursion (call stack)
Exploration shape	expanding rings by distance from $s$	plunge deep, then backtrack
Mark visited	at enqueue (each vertex queued exactly once)	at entry (recursive) / at pop (iterative, tolerates dup pushes)
Signature power	shortest unweighted distance $\delta(s,v)$	finishing-time order $\Rightarrow$ topo sort, cycles
Vertex order means	distance from source	not distance — depends on neighbor order
Time (list / matrix)	$\Theta(V+E)$ / $\Theta(V^2)$	$\Theta(V+E)$ / $\Theta(V^2)$
Extra space	$O(V)$	$O(V)$
Pitfall	breaks for weighted shortest paths (use Dijkstra, Ch. 29)	record at finish + reverse for topo sort, not pre-order

BFS (distances + parents):

dist[s]=0; parent[s]=None; queue=[s]
while queue: v=popleft
  for w in adj[v]:
    if w not in dist: dist[w]=dist[v]+1; parent[w]=v; enqueue w

DFS (recursive pre-order):

visit(v): mark v; order += v
          for w in adj[v]: if w unvisited: visit(w)

Topological sort (DAG): DFS; finish.append(v) after the recursion loop; then finish.reverse().

Shortest path: run BFS, then follow parent[t] -> ... -> s, reverse.

Result	Statement
BFS correctness	After BFS from $s$, $\mathrm{dist}[v]=\delta(s,v)$ = min #edges on an $s$–$v$ path, for all reachable $v$. Proof: queue invariant (values span two consecutive ints) + induction on distance.
Traversal time (list)	$\Theta(V+E)$. $\Theta(V)$ for vertices + $\sum_v\deg(v)=2E$ scan work (handshaking lemma, Ch. 27).
Traversal time (matrix)	$\Theta(V^2)$ — each neighbor listing scans a full row. Equals list bound only when dense.
Components partition $V$	"mutually reachable" is an equivalence relation (Ch. 12) $\Rightarrow$ disjoint classes = components.
Spanning tree (intro)	tree edges of any BFS/DFS on a connected graph = a spanning tree: all $n$ vertices, $n-1$ edges, no cycle (Ch. 32 finds the cheapest).
Topo order exists	iff the directed graph is a DAG (no directed cycle). A directed cycle forces a vertex before itself.
Finishing-time property	In a DAG, if $a\to b$ then $a$ finishes after $b$ $\Rightarrow$ reversed finish order is topological.

Shortest path, all edges equal → BFS.
Topological order / cycle detection / recurse into structure → DFS.
Reachability, connectivity, components → either traversal (both reach the same set).
Graph sparse / mostly traverse → adjacency list.
Graph dense / mostly single-edge tests → adjacency matrix.
Edges weighted → neither; use Dijkstra (Ch. 29) / Bellman–Ford.

Pitfall	Fix
"Adjacency list is always best"	Dense graphs: matrix is better (space + $O(1)$ edge test).
Marking BFS visited at dequeue	Mark at enqueue → each vertex queued once, at true shortest distance.
Using BFS for weighted shortest paths	Ring argument fails; use Dijkstra.
Topo sort = DFS pre-order	Must be post-order, reversed; pre-order passes on lucky inputs only.
Undirected cycle test on a directed graph	Direction matters; a diamond DAG looks like an undirected cycle. Track vertices on the recursion stack.
Forgetting the parent edge in undirected cycle check	Exclude the single parent edge; any other edge to a visited vertex = cycle.
Recursive DFS on a very deep graph	Call-stack overflow → use the iterative (explicit-stack) form.

Function	Returns	Builds toward
`bfs(g, s)`	`(dist, parent)` dicts	"degrees of separation"; refactors into `dijkstra` (Ch. 29); capstone Track B
`dfs(g, s)`	pre-order visiting list	cycle detection; `topological_sort`; Part V algorithms

Signatures are canonical — keep them stable so later modules compose.