Graph Representations and Traversal

Almost every interesting structure (a road map, a social network, the dependencies between tasks, the states of a puzzle) is a set of things and the connections between them. A graph is the mathematical object that captures exactly this and nothing more. Mastering a handful of graph algorithms gives you a lever on a startlingly wide range of problems; Skiena's blunt advice is that the hardest part is usually recognizing that your problem is a graph problem in disguise.¹

What is a graph?

If edges have no direction, so that an edge $\left\{u,v\right\}$ connects $u$ and $v$ symmetrically, the graph is undirected. If each edge is an ordered pair $(u,v)$ pointing from $u$ to $v$, the graph is directed (a digraph). We write $n=\left|V\right|$ for the number of vertices and $m=\left|E\right|$ for the number of edges; inside asymptotic notation we abbreviate these to $V$ and $E$, writing bounds like $O(V+E)$.

The definition is fussy for a reason: every clause rules out a pathology. A graph is finite (otherwise we cannot index vertices), edges are unordered pairs $\left\{u,v\right\}$ (ordered pairs would give a digraph), there are no parallel edges (since $E$ is a set, not a multiset), and no self-loops (since $\left|e\right|=2$ for every $e\in E\subseteq \left(\genfrac{}{}{0ex}{}{V}{2}\right)$). Relaxing any one clause yields a richer object: a multigraph, a digraph, and so on.

A few terms recur constantly:

• Vertices $u$ and $v$ are adjacent if an edge joins them; that edge $e=\left\{u,v\right\}$ is incident on both, which are its endpoints.
• The degree $\mathrm{deg}(v)=\left|\left\{e:e\text{ is incident on }v\right\}\right|$ counts the edges touching $v$. In a digraph $e=(u,v)$ leaves $u$ (its tail) and arrives at $v$ (its head), and we split degree into $in-deg(v)$ and $out-deg(v)$.
• The handshake lemma falls straight out of counting incidences both ways: ${\sum }_{v\in V}\mathrm{deg}(v)=2\left|E\right|$ in a graph, and ${\sum }_{v}in-deg(v)=\left|E\right|={\sum }_{v}out-deg(v)$ in a digraph.
• A walk is an alternating sequence $(v_0,e_1,v_1,e_2,\dots ,e_{\ell },v_{\ell })$ respecting incidence, of length $\ell$. A walk with $v_0=v_{\ell }$ is closed. A path is a walk with no repeated vertices; a cycle is a closed walk whose vertices are distinct except for the shared endpoint (length $\ge 3$ in a graph, $\ge 2$ in a digraph). Beware: many texts overload path to mean walk, but we keep them separate.
• An undirected graph is connected if a path joins every pair of vertices; a digraph is strongly connected if a directed path runs both ways between every pair. A connected component is a maximal connected subgraph.
• The distance $d(u,v)$ is the length of the shortest path from $u$ to $v$ (directed, for digraphs), or $\infty$ if $v$ is unreachable from $u$.
• A graph may carry a weight $w(u,v)$ on each edge (a length, cost, or capacity) that later lessons will exploit.

Here is a small undirected graph on five vertices that we will use throughout this lesson:

A graph is bounded in size: every simple graph has at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$ edges, so $m=O(n^2)$. A graph is sparse when $m$ is close to $n$ and dense when $m$ is close to $n^2$. This single distinction governs which representation, and sometimes which algorithm, to choose.

Two ways to store a graph

We need a concrete data structure before we can compute anything. The two standard choices trade space against the speed of one key query: is there an edge from $u$ to $v$?

Adjacency list. Keep an array indexed by vertex; entry $u$ holds a list of $u$'s neighbors. Total space is $\Theta (V+E)$, one slot per vertex plus one list node per edge (two, in an undirected graph, since each edge appears on both endpoints' lists). Listing a vertex's neighbors is immediate, which is exactly what traversals need.

Adjacency matrix. Keep an $n\times n$ matrix $A$ with $A[u][v]=1$ when edge $(u,v)$ exists and $0$ otherwise (or the weight, for a weighted graph). Testing a specific edge is $O(1)$, but the matrix always occupies $\Theta (V^2)$ space regardless of how few edges there are, and listing a vertex's neighbors costs $\Theta (V)$ because we must scan a whole row.

Concretely, here is the five-vertex graph above stored both ways. The list keeps one short neighbor-list per vertex; the matrix spends a full $5\times 5$ grid of bits, symmetric across the diagonal because the graph is undirected:

CLRS, Skiena, and Erickson all reach the same verdict: the adjacency list is the default.² Real graphs are usually sparse, and the linear-space, fast-to-iterate list is what makes the $O(V+E)$ traversals below possible. Reach for the matrix only when the graph is dense, when you need constant-time edge tests, or when an algorithm is naturally phrased in linear-algebra terms.

One traversal to rule them all

Before specializing, it pays to see that BFS and DFS are the same algorithm. This is made explicit with a deliberately generic skeleton called Whatever-First Search: grow a frontier of discovered-but-unprocessed vertices, repeatedly pull one out, and push each of its undiscovered neighbors in. The only freedom is which vertex you pull next, and that is decided entirely by the data structure holding the frontier.

The $\pi$ pointers always carve out a tree (or forest) rooted at $s$, the search tree, because each vertex is discovered exactly once, from exactly one parent. What changes is the shape of that tree, and it is fixed by one choice:

This is the unifying idea to carry forward: BFS is the queue instantiation, DFS is the stack instantiation, and the weighted shortest-path and minimum-spanning-tree algorithms of later lessons are just Whatever-First-Search with a priority queue. Everything below specializes this one skeleton.

The choice of bag shows up as the shape of the search tree. Run both on the same little graph from $s$ (ties broken alphabetically): the queue grows a short, bushy tree that hugs $s$ at every depth, while the stack grows one long descending spine, diving as far as it can before backing up.

Breadth-first search

The most basic question we can ask is: starting from a source $s$, which vertices can I reach, and how far away is each? Breadth-first search (BFS) is Whatever-First-Search with a queue. It explores in rings of increasing distance: first $s$ itself, then all neighbors of $s$, then everything new one step beyond them, and so on. The first-in-first-out discipline is exactly what enforces this level-by-level order; the oldest-discovered vertex always sits at the shallowest depth still unfinished.

As it runs, BFS computes for each vertex $v$ a distance $v.d$, the fewest edges (hops) on any path from $s$ to $v$, and a predecessor $v.\pi$, the vertex from which $v$ was discovered. The predecessors form the breadth-first tree (or shortest-path tree) $\left\{(v.\pi ,v):v\text{ visited}\right\}$. We refine the single visited flag of the skeleton into three colors: white vertices are undiscovered, gray ones are discovered but still in the queue, and black ones are finished.

Shortest hops, and why it is correct. Write $\mathrm{dist}[s][v]$ for the true distance from $s$ to $v$, the length of the shortest directed path. The claim BFS delivers is the cleanest possible: $v.d=\mathrm{dist}[s][v]$ for every $v$. Two facts drive the proof:

• The queue is sorted by depth. At every moment the $d$-values in $Q$ span at most two consecutive layers $k,k+1$, and never decrease as we dequeue. (BFS only ever appends $v.d=u.d+1$ to the back.)
• $v.d\ge \mathrm{dist}[s][v]$ always, because $v.d$ is the length of an actual $s\to v$ path (trace the $\pi$ pointers), and no path beats the shortest one.

For the reverse inequality, induct on $\mathrm{dist}[s][v]=k$. A vertex at true distance $k$ has some neighbor $u$ at true distance $k-1$; by induction $u.d=k-1$, and since all depth-$(k-1)$ vertices are dequeued before any depth-$k$ vertex is processed, $v$ is white when BFS scans $u$'s list and gets $v.d=u.d+1=k$. Hence $v.d=\mathrm{dist}[s][v]$, and following $\pi$ pointers from $v$ back to $s$ traces an actual shortest path in reverse: the unique $s$-to-$v$ path in the BFS tree.

Running time. Initialization touches every vertex once: $\Theta (V)$. Each vertex is enqueued and dequeued exactly once (only white vertices are enqueued, and they are immediately grayed), and when we dequeue $u$ we scan its adjacency list once. The scans together examine every edge a constant number of times, for $\Theta (E)$ total. Hence BFS runs in $O(V+E)$, linear in the size of the graph, the gold standard for graph algorithms.³

A worked run. Take this small digraph and run BFS from $s$. The queue evolves $[s]\to [a,b,c]\to [b,c,e]\to [c,e]\to [e,g]\to [g,f]\to [f]\to []$, discovering vertices in the order $s,a,b,c,e,g,f$. The resulting $d$-values sort the vertices into layers by distance from $s$, which let us read off shortest BFS distances directly:

Thick edges are tree edges $(v.\pi ,v)$; gray dashed edges point at vertices already discovered, so BFS skips them. Reading off $d$: $s.d=0$; $a.d=b.d=c.d=1$; $e.d=g.d=2$; $f.d=3$. Vertex $d$ has no path from $s$, so $d.d=\infty$, and it never enters the queue. The tree path from $s$ down to any vertex spells out a shortest route in hops.

Reachability and components, for free. The skeleton already solves more than distances. To list the connected components of an undirected graph, loop over all vertices and start a fresh search from each still-unvisited one, tagging every vertex it reaches with the current component number:

Each search marks exactly one component, and every vertex is visited once, so the whole sweep is still $O(V+E)$. Because we only used the visited flag, any instantiation works here — swap in DFS and nothing changes. This is the payoff of the unifying view: connectivity is a Whatever-First-Search property, not a BFS one.

Depth-first search

Where BFS fans out in rings, depth-first search (DFS) plunges. It is Whatever-First-Search with a stack: pulling the newest discovered vertex means we always descend from where we just were. From a vertex it follows an edge to an unvisited neighbor, then a neighbor of that, going as deep as possible before backtracking to the most recent vertex with an unexplored edge. The LIFO stack is usually left implicit — it is the recursion call stack.

DFS's gift is a pair of timestamps on each vertex $v$: a discovery (or start) time, which we write $s_v$, stamped when $v$ first turns gray, and a finish time $f_v$, stamped when $v$ turns black after all its descendants are done. A single global clock $time$ ticks once per stamp, so on $n$ vertices every value in $1,2,\dots ,2n$ is used exactly once. Unlike BFS, the outer driver restarts DFS from any leftover white vertex, so it covers disconnected pieces too, producing a depth-first forest rather than a single tree.

Like BFS, DFS runs in $\Theta (V+E)$: the initialization and the outer loop cost $\Theta (V)$, and $\text{DFS-Visit}$ is called exactly once per vertex (only on white vertices, which it immediately grays), scanning each adjacency list once for $\Theta (E)$ total.

A worked DFS, and the nesting structure

Run $\text{DFS}$ on the digraph below, starting at $s$ and breaking ties alphabetically. Each vertex is labeled $s_v/f_v$. Thick edges are tree edges (the depth-first forest); the dashed edges are non-tree edges, classified next.

The discovery and finish times nest like balanced parentheses. Write each vertex's interval $[s_v,f_v]$. For any two vertices $u$ and $v$, exactly one of three things holds, since they can never partially overlap:

• the intervals are disjoint, and neither vertex is a descendant of the other (they are incomparable), or
• one interval contains the other, and the contained vertex is a descendant of the container in the DFS forest.

This is the nesting theorem (CLRS calls it the parenthesis theorem), and it makes the recursion visible.⁴ Drawing each interval $[s_v,f_v]$ as a bar along the time axis turns the forest into a literal stack of nested brackets — a bar sits strictly inside another exactly when the inner vertex is a descendant of the outer:

Above, $[s_x,f_x]=[4,5]\subset [3,6]=[s_y,f_y]\subset [2,9]=[s_w,f_w]$, so $x$ is a descendant of $y$ is a descendant of $w$. Two companions sharpen it:

• White-path theorem. $v$ becomes a descendant of $u$ if and only if, at the moment $u$ is discovered (time $s_u$), there is a path $u⇝v$ consisting entirely of still-white vertices. This is the cleanest test for what will end up under $u$.
• Cycle theorem. Every back edge lies on a cycle, and every cycle contains at least one back edge. Equivalently, a digraph is acyclic iff DFS finds no back edge, the engine behind cycle detection and topological sort.

Classifying edges

As DFS traverses an edge $(u,v)$, the color of $v$ at that moment reveals what kind of edge it is, a classification that drives the algorithms of the next lessons. In the worked digraph above:

• Tree edge. $v$ is white: we set $v.\pi =u$, so the edge is $(v.\pi ,v)$. We discover $v$ through this edge; it joins the depth-first forest (e.g. $s\to w$, $w\to y$).
• Back edge. $v$ is gray, an ancestor of $u$ still on the recursion stack ($z\to s$, since $[s_z,f_z]\subset [s_s,f_s]$). A digraph has a back edge iff it has a cycle, the linchpin of cycle detection and topological sort.
• Forward edge. $v$ is black and a descendant of $u$ ($s\to z$: a non-tree edge to an already-finished descendant).
• Cross edge. $v$ is black and not a descendant of $u$ ($z\to x$, or the edge $r\to q$ between separate tree branches).

In an undirected graph the picture simplifies: every edge is either a tree edge or a back edge, since forward and cross edges cannot occur, because exploring an edge from either endpoint reaches the other while it is still gray.

BFS or DFS?

They are one algorithm, $\text{Whatever-First-Search}$, read with two different bags. Both are $O(V+E)$ linear-time skeletons; the order of removal is the only difference, and it dictates the structure each exposes.

Choose BFS when distance-in-hops matters; choose DFS when you need a graph's recursive structure, which, as the next two lessons show, is exactly what topological sorting and strong connectivity demand. And keep the frame in mind: swap the bag for a priority queue and the very same skeleton becomes Dijkstra and Prim.

Takeaways

• A graph $G=(V,E)$ models things and their connections; the sparse-versus-dense distinction drives every representation choice.
• Prefer the adjacency list ($\Theta (V+E)$ space, fast neighbor iteration); use the adjacency matrix ($\Theta (V^2)$) only for dense graphs or constant-time edge tests.
• $\text{Whatever-First-Search}$ is the one skeleton: grow a frontier bag, and let the bag's discipline pick the next vertex. A queue gives BFS, a stack gives DFS, a priority queue gives the weighted algorithms to come.
• BFS explores in rings from a source and computes $\mathrm{dist}[s][v]$, the shortest path in hops, building a breadth-first tree via a FIFO queue.
• DFS plunges and backtracks, stamping start/finish times $[s_v,f_v]$ that nest like parentheses (nesting + white-path theorems) and classify edges; most importantly, a back edge exists exactly when the graph has a cycle.
• Both traversals run in $O(V+E)$, linear in the graph's size, and either one labels connected components for free.