---
title: Graph Representations and Traversal
module: Graphs
moduleNumber: 6
lessonNumber: 1
order: 601
summary: |
  A graph captures _relationships_ — who connects to whom. We fix the
  vocabulary, weigh the two standard representations (adjacency list versus
  matrix), then meet the single search skeleton behind everything that follows:
  Whatever-First-Search, and its breadth-first reading, which finds shortest
  paths by number of edges in $O(V + E)$.
topics: [Graph Representations, Graph Traversal]
sources:
  - book: CLRS
    ref: "Ch. 22 — Elementary Graph Algorithms"
  - book: Skiena
    ref: "§5 — Graph Traversal"
  - book: Erickson
    ref: "Ch. 6 — Graph Search"
practice:
  - title: 'Flood Fill'
    slug: flood-fill
    difficulty: Easy
  - title: 'Number of Islands'
    slug: number-of-islands
    difficulty: Medium
  - title: 'Rotting Oranges'
    slug: rotting-oranges
    difficulty: Medium
  - title: 'Word Ladder'
    slug: word-ladder
    difficulty: Hard
---


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. A handful of graph algorithms covers a
wide range of problems; Skiena's advice is that the hardest part is usually
_recognizing_ that a problem is a graph problem.[^skiena-graph]

## What is a graph?

> **Definition (Graph).** A graph $G = (V, E)$ is a finite set $V$ of **vertices** together with a
> set $E$ of **edges**, where each edge joins a pair of vertices.

If edges have no direction, so that an edge $\set{u, v}$ 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 = \abs{V}$ for the number of vertices and $m = \abs{E}$ for the
number of edges; inside [asymptotic notation](/algorithms/foundations/asymptotic-analysis) 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 $\set{u, v}$ (ordered pairs would give a digraph), there are
**no parallel edges** (since $E$ is a _set_, not a multiset), and **no self-loops**
(since $\abs{e} = 2$ for every $e \in E \subseteq \binom{V}{2}$). 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 =
  \set{u, v}$ is **incident** on both, which are its **endpoints**.
- The **degree** $\deg(v) = \abs{\set{e : e \text{ is incident on } v}}$ 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
  $\operatorname{in-deg}(v)$ and $\operatorname{out-deg}(v)$.
- The **handshake lemma** falls straight out of counting incidences both ways:
  $\sum_{v \in V} \deg(v) = 2\abs{E}$ in a graph, and $\sum_{v}
  \operatorname{in-deg}(v) = \abs{E} = \sum_{v} \operatorname{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 $\geq 3$ in a graph, $\geq 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:

$$
% caption: A small undirected graph on five vertices used throughout the lesson.
\begin{tikzpicture}[every node/.style={circle, draw, minimum size=8mm, font=\small},
  node distance=18mm]
  \node (s) {$s$};
  \node (a) [above right=10mm and 16mm of s] {$a$};
  \node (b) [below right=10mm and 16mm of s] {$b$};
  \node (c) [right=18mm of a] {$c$};
  \node (d) [right=18mm of b] {$d$};
  \draw (s) -- (a);
  \draw (s) -- (b);
  \draw (a) -- (b);
  \draw (a) -- (c);
  \draw (b) -- (d);
  \draw (c) -- (d);
\end{tikzpicture}
$$

A graph is bounded in size: every simple graph has at most
$\binom{n}{2} = \tfrac{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 — just
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.

| Operation | Adjacency list | Adjacency matrix |
| --- | --- | --- |
| Space | $\Theta(V + E)$ | $\Theta(V^2)$ |
| Test edge $(u,v)$? | $O(\deg u)$ | $\Theta(1)$ |
| List neighbors of $u$ | $\Theta(\deg u)$ | $\Theta(V)$ |
| Add an edge | $O(1)$ | $\Theta(1)$ |
| Iterate over all edges | $\Theta(V + E)$ | $\Theta(V^2)$ |
| Best when | graph is **sparse** | graph is **dense** |

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:

$$
% caption: The five-vertex graph stored two ways: adjacency lists (left) and the symmetric
%          $0/1$ adjacency matrix (right).
\begin{tikzpicture}[font=\small]
  \definecolor{acc}{HTML}{2348F2}
  % --- adjacency lists ---
  \node[font=\footnotesize] at (0.7,3.0) {\textbf{adjacency list}};
  \foreach \v/\y/\lst in {s/2.4/{a, b}, a/1.8/{s, b, c}, b/1.2/{s, a, d}, c/0.6/{a, d}, d/0/{b, c}} {
    \node[draw, minimum size=5mm, fill=acc!12] (n\v) at (0,\y) {$\v$};
    \draw[->, black] (0.42,\y) -- (0.85,\y);
    \node[anchor=west, font=\footnotesize] at (1.0,\y) {\lst};
  }
  % --- adjacency matrix ---
  \begin{scope}[xshift=52mm]
    \node[font=\footnotesize] at (1.5,3.0) {\textbf{adjacency matrix}};
    \foreach \c/\x in {s/0, a/0.6, b/1.2, c/1.8, d/2.4}
      \node[font=\footnotesize\bfseries] at (\x,2.5) {$\c$};
    \foreach \r/\y in {s/2.0, a/1.4, b/0.8, c/0.2, d/-0.4}
      \node[font=\footnotesize\bfseries] at (-0.6,\y) {$\r$};
    \foreach \row/\y in {{0,1,1,0,0}/2.0, {1,0,1,1,0}/1.4, {1,1,0,0,1}/0.8, {0,1,0,0,1}/0.2, {0,0,1,1,0}/-0.4} {
      \foreach \val [count=\i from 0] in \row {
        \pgfmathsetmacro\x{0.6*\i}
        \ifnum\val=1
          \node[draw, minimum size=5mm, fill=acc!15] at (\x,\y) {$1$};
        \else
          \node[draw, minimum size=5mm] at (\x,\y) {$0$};
        \fi
      }
    }
  \end{scope}
\end{tikzpicture}
$$

The row-scan cost is the decisive one. Every traversal below spends its time
asking "give me the neighbors of $u$," once per vertex. With lists, the total
work is $\sum_{u \in V} \Theta(1 + \deg u) = \Theta(V) + \Theta(E)$ by the
handshake lemma — that is where the $O(V + E)$ bound comes from. With a matrix,
the same sweep costs $\sum_{u \in V} \Theta(V) = \Theta(V^2)$ _no matter how few
edges exist_. On a sparse graph with $n = 10^6$ vertices and $m = 3 \times 10^6$
edges, the list stores about $n + 2m = 7 \times 10^6$ entries, while the matrix
stores $n^2 = 10^{12}$ cells; a single BFS does $7 \times 10^6$ units of work
versus $10^{12}$. The break-even point sits around $m = \Theta(n^2)$: only when
most possible edges are present does the matrix's $\Theta(1)$ edge test and
cache-friendly layout pay for its quadratic footprint.

CLRS, Skiena, and Erickson all reach the same verdict: the **adjacency list**
is the default.[^clrs-rep] 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 (powers of $A$
count walks; spectral methods want the matrix by definition).

::impl{algo="adjacency_matrix"}

## 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**.

```algorithm
caption: $\textsc{Whatever-First-Search}(G, s)$ — the generic skeleton
number: 1
foreach vertex $v \in V$ do
  $v.visited \gets \text{false}$
  $v.\pi \gets \text{nil}$
$s.visited \gets \text{true}$
put $s$ into the bag $B$
while $B \neq \emptyset$ do
  take a vertex $u$ out of $B$ // bag decides who
  foreach $v$ adjacent to $u$ do
    if not $v.visited$ then
      $v.visited \gets \text{true}$
      $v.\pi \gets u$
      put $v$ into the bag $B$
```

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:

| Bag $B$ | Order of removal | Specialization |
| --- | --- | --- |
| **Queue** (FIFO) | oldest first | $\textsc{BFS}$ — explores in rings |
| **Stack** (LIFO) | newest first | $\textsc{DFS}$ — plunges and backtracks |
| **Priority queue** | cheapest first | Dijkstra / Prim (later lessons) |

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/graphs/minimum-spanning-trees)
algorithms of later lessons are just Whatever-First-Search with a priority queue.
Everything below specializes this one skeleton.

::impl{algo="whatever_first_search"}

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.

$$
% caption: Same graph, same source: the queue (BFS) builds a shallow bushy tree, the stack
%          (DFS) a deep spine.
\begin{tikzpicture}[
  >=Stealth,
  V/.style={circle, draw, minimum size=7mm, font=\small},
  R/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=7mm, font=\small},
  tree/.style={->, very thick}]
  \definecolor{acc}{HTML}{2348F2}
  % ---- BFS ----
  \node[font=\footnotesize] at (1.4,1.0) {BFS (queue)};
  \node[R] (bs) at (1.4,0) {$s$};
  \node[V] (ba) at (0,-1.4) {$a$};
  \node[V] (bb) at (1.4,-1.4) {$b$};
  \node[V] (bc) at (2.8,-1.4) {$c$};
  \node[V] (bd) at (1.4,-2.8) {$d$};
  \draw[tree] (bs) -- (ba);
  \draw[tree] (bs) -- (bb);
  \draw[tree] (bs) -- (bc);
  \draw[tree] (bb) -- (bd);
  % ---- DFS ----
  \begin{scope}[xshift=58mm]
    \node[font=\footnotesize] at (1.4,1.0) {DFS (stack)};
    \node[R] (ds) at (1.4,0) {$s$};
    \node[V] (da) at (0.7,-1.4) {$a$};
    \node[V] (db) at (0,-2.8) {$b$};
    \node[V] (dd) at (0.7,-4.2) {$d$};
    \node[V] (dc) at (2.1,-1.4) {$c$};
    \draw[tree] (ds) -- (da);
    \draw[tree] (da) -- (db);
    \draw[tree] (db) -- (dd);
    \draw[tree] (ds) -- (dc);
  \end{scope}
\end{tikzpicture}
$$

## 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 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**) $\set{(v.\pi,\, v) : v \text{ visited}}$. 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.

```algorithm
caption: $\textsc{BFS}(G, s)$ — shortest distances in hops from $s$
number: 2
foreach vertex $u \in V \setminus \set{s}$ do
  $u.color \gets \text{white}$
  $u.d \gets \infty$
  $u.\pi \gets \text{nil}$
$s.color \gets \text{gray}$ // discover source
$s.d \gets 0$
$s.\pi \gets \text{nil}$
$Q \gets \emptyset$
enqueue$(Q, s)$
while $Q \neq \emptyset$ do
  $u \gets$ dequeue$(Q)$
  foreach $v$ adjacent to $u$ do
    if $v.color = \text{white}$ then // first time reaching v
      $v.color \gets \text{gray}$
      $v.d \gets u.d + 1$
      $v.\pi \gets u$
      enqueue$(Q, v)$
  $u.color \gets \text{black}$
return $d$ and $\pi$
```

Write $\dist[s][v]$ for the _true_ distance from $s$ to $v$, the
length of the shortest directed path. BFS computes it exactly.

> **Theorem (BFS correctness).** After $\textsc{BFS}(G, s)$, every vertex $v$ has
> $v.d = \dist[s][v]$, and the $\pi$ pointers trace a shortest
> $s$-to-$v$ path in reverse.

> **Proof.** Collect the vertices into **layers** $L_k = \set{v :
> \dist[s][v] = k}$, and establish two facts first.
>
> - _The queue is sorted by depth._ At every moment the $d$-values in $Q$ are
>   non-decreasing from front to back and span at most two consecutive values
>   $k, k{+}1$: BFS only ever appends $v.d = u.d + 1$ to the back, where $u.d$ is
>   the current front value. Consequently all vertices with $d$-value $k$ are
>   dequeued before any vertex with $d$-value $k{+}1$.
> - _$v.d \geq \dist[s][v]$ for every $v$, at all times._ When BFS
>   sets $v.d = u.d + 1$ it has exhibited an actual walk from $s$ to $v$ (follow
>   the $\pi$ pointers back), and no walk is shorter than the shortest path.
>
> Now induct on $k$ with the hypothesis: _every vertex of $L_k$ is discovered
> with $d$-value exactly $k$, and all of $L_k$ enters the queue before any vertex
> of $L_{k+1}$ is dequeued._ The base case is $L_0 = \set{s}$ with $s.d = 0$.
> For the step, let $v \in L_{k+1}$. Some shortest path $s \rightsquigarrow v$ has
> a penultimate vertex $u \in L_k$; by the hypothesis $u.d = k$, and $u$ is
> dequeued before any depth-$(k{+}1)$ vertex. When BFS scans $u$'s list, either
> $v$ is still white and gets $v.d = u.d + 1 = k + 1$, or $v$ was already
> discovered by an earlier vertex of depth $\leq k$ — and then $v.d \leq k+1$
> combined with the lower bound $v.d \geq k+1$ again forces $v.d = k+1$. Either
> way $v$ enters the queue while depth-$k$ vertices are still being processed,
> before any depth-$(k{+}1)$ vertex is dequeued, closing the induction. Finally,
> $v.\pi$ satisfies $v.\pi.d = v.d - 1$, so following $\pi$ pointers from $v$
> steps down one layer at a time and traces a shortest path in reverse: _the_
> unique $s$-to-$v$ path in the BFS tree. $\qed$

**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.[^clrs-bfs]

**A worked run.** Take the digraph with vertices $\set{s, a, b, c, d, e, f, g}$
and directed edges

$$
s \to a, \quad s \to b, \quad s \to c, \quad a \to b, \quad b \to e, \quad
c \to e, \quad c \to g, \quad e \to f, \quad d \to c,
$$

run BFS from $s$, and scan each adjacency list alphabetically. Every row below
is one iteration of the **while** loop: dequeue $u$, scan $u$'s list, enqueue
each white neighbor with distance $u.d + 1$.

| Dequeue $u$ | $u$'s list | Newly discovered ($v.d,\ v.\pi$) | Queue after |
| --- | --- | --- | --- |
| — (init) | — | $s.d = 0$ | $\langle s \rangle$ |
| $s$ | $a, b, c$ | $a.d{=}1$, $b.d{=}1$, $c.d{=}1$, all $\pi = s$ | $\langle a, b, c \rangle$ |
| $a$ | $b$ | none ($b$ gray) | $\langle b, c \rangle$ |
| $b$ | $e$ | $e.d = 2$, $e.\pi = b$ | $\langle c, e \rangle$ |
| $c$ | $e, g$ | $g.d = 2$, $g.\pi = c$ ($e$ gray) | $\langle e, g \rangle$ |
| $e$ | $f$ | $f.d = 3$, $f.\pi = e$ | $\langle g, f \rangle$ |
| $g$ | — | none | $\langle f \rangle$ |
| $f$ | — | none | $\langle\, \rangle$ |

Two things to watch in the table. The $d$-values leaving the queue never
decrease ($0, 1, 1, 1, 2, 2, 3$), the sortedness the proof leaned on. And each
non-tree edge is _examined_ but discovers nothing: $a \to b$ arrives while $b$ is
gray, $c \to e$ while $e$ is gray. The resulting $d$-values sort the vertices
into **layers** by distance from $s$, which let us read off shortest
[BFS distances](/algorithms/graphs/shortest-paths) directly:

$$
% caption: BFS tree from $s$ with vertices sorted into distance layers $d = 0$ to $3$.
\begin{tikzpicture}[
  >=Stealth,
  V/.style={circle, draw, minimum size=8mm, font=\small},
  tree/.style={->, very thick},
  cross/.style={->, black, dashed}]
  % layer 0
  \node[V] (s) at (2.8,4.5) {$s$};
  % layer 1
  \node[V] (a) at (0.8,3.0) {$a$};
  \node[V] (b) at (2.8,3.0) {$b$};
  \node[V] (c) at (4.8,3.0) {$c$};
  % layer 2
  \node[V] (e) at (2.8,1.5) {$e$};
  \node[V] (g) at (4.8,1.5) {$g$};
  % layer 3
  \node[V] (f) at (2.8,0) {$f$};
  \node[V] (d) at (7.0,3.0) {$d$};
  % tree edges (solid) — the BFS / shortest-path tree
  \draw[tree] (s) -- (a);
  \draw[tree] (s) -- (b);
  \draw[tree] (s) -- (c);
  \draw[tree] (b) -- (e);
  \draw[tree] (c) -- (g);
  \draw[tree] (e) -- (f);
  % non-tree edges (already-visited targets)
  \draw[cross] (a) -- (b);
  \draw[cross] (c) -- (e);
  \draw[cross] (d) -- (c);
  % layer labels
  \node[font=\footnotesize] at (-0.4,4.5) {$d=0$};
  \node[font=\footnotesize] at (-0.4,3.0) {$d=1$};
  \node[font=\footnotesize] at (-0.4,1.5) {$d=2$};
  \node[font=\footnotesize] at (-0.4,0)   {$d=3$};
\end{tikzpicture}
$$

Thick edges are **tree edges** $(v.\pi, v)$; 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 — BFS computes distances _from the source_, and
unreachable vertices simply stay white. The tree path from $s$ down to any
vertex spells out a shortest route in hops.

The same run, viewed as snapshots between layers, shows the queue acting as a
moving ring: at any instant it holds the **frontier**, the gray vertices whose
edges have not been scanned yet, and each pass pushes the ring one hop outward:

$$
% caption: Four snapshots of the BFS from $s$. Blue-ringed vertices are the frontier
%          (gray, in the queue), shaded vertices are finished (black), plain vertices are
%          undiscovered (white). Thick edges discovered the current frontier.
\begin{tikzpicture}[
  >=Stealth,
  W/.style={circle, draw, minimum size=5.5mm, font=\scriptsize, inner sep=1pt},
  Fr/.style={circle, draw=acc, very thick, fill=acc!18, minimum size=5.5mm, font=\scriptsize, inner sep=1pt},
  Dn/.style={circle, draw=black, fill=black!12, minimum size=5.5mm, font=\scriptsize, inner sep=1pt},
  ed/.style={->, black},
  td/.style={->, acc, very thick},
  pl/.style={font=\footnotesize},
  qq/.style={font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % ---------- panel 1: before layer 1 ----------
  \begin{scope}
    \node[pl] at (2.2,3.4) {start};
    \node[Fr] (p1s) at (1.7,2.6) {$s$};
    \node[W] (p1a) at (0.6,1.75) {$a$};
    \node[W] (p1b) at (1.7,1.75) {$b$};
    \node[W] (p1c) at (2.8,1.75) {$c$};
    \node[W] (p1e) at (1.7,0.9) {$e$};
    \node[W] (p1g) at (2.8,0.9) {$g$};
    \node[W] (p1f) at (1.7,0.05) {$f$};
    \node[W] (p1d) at (3.9,1.75) {$d$};
    \draw[ed] (p1s) -- (p1a); \draw[ed] (p1s) -- (p1b); \draw[ed] (p1s) -- (p1c);
    \draw[ed] (p1a) -- (p1b); \draw[ed] (p1b) -- (p1e); \draw[ed] (p1c) -- (p1e);
    \draw[ed] (p1c) -- (p1g); \draw[ed] (p1e) -- (p1f); \draw[ed] (p1d) -- (p1c);
    \node[qq] at (2.2,-0.75) {Q: s};
  \end{scope}
  % ---------- panel 2: layer 1 discovered ----------
  \begin{scope}[xshift=62mm]
    \node[pl] at (2.2,3.4) {layer 1 discovered};
    \node[Dn] (p2s) at (1.7,2.6) {$s$};
    \node[Fr] (p2a) at (0.6,1.75) {$a$};
    \node[Fr] (p2b) at (1.7,1.75) {$b$};
    \node[Fr] (p2c) at (2.8,1.75) {$c$};
    \node[W] (p2e) at (1.7,0.9) {$e$};
    \node[W] (p2g) at (2.8,0.9) {$g$};
    \node[W] (p2f) at (1.7,0.05) {$f$};
    \node[W] (p2d) at (3.9,1.75) {$d$};
    \draw[td] (p2s) -- (p2a); \draw[td] (p2s) -- (p2b); \draw[td] (p2s) -- (p2c);
    \draw[ed] (p2a) -- (p2b); \draw[ed] (p2b) -- (p2e); \draw[ed] (p2c) -- (p2e);
    \draw[ed] (p2c) -- (p2g); \draw[ed] (p2e) -- (p2f); \draw[ed] (p2d) -- (p2c);
    \node[qq] at (2.2,-0.75) {Q: a, b, c};
  \end{scope}
  % ---------- panel 3: layer 2 discovered ----------
  \begin{scope}[yshift=-52mm]
    \node[pl] at (2.2,3.4) {layer 2 discovered};
    \node[Dn] (p3s) at (1.7,2.6) {$s$};
    \node[Dn] (p3a) at (0.6,1.75) {$a$};
    \node[Dn] (p3b) at (1.7,1.75) {$b$};
    \node[Dn] (p3c) at (2.8,1.75) {$c$};
    \node[Fr] (p3e) at (1.7,0.9) {$e$};
    \node[Fr] (p3g) at (2.8,0.9) {$g$};
    \node[W] (p3f) at (1.7,0.05) {$f$};
    \node[W] (p3d) at (3.9,1.75) {$d$};
    \draw[ed] (p3s) -- (p3a); \draw[ed] (p3s) -- (p3b); \draw[ed] (p3s) -- (p3c);
    \draw[ed] (p3a) -- (p3b); \draw[td] (p3b) -- (p3e); \draw[ed] (p3c) -- (p3e);
    \draw[td] (p3c) -- (p3g); \draw[ed] (p3e) -- (p3f); \draw[ed] (p3d) -- (p3c);
    \node[qq] at (2.2,-0.75) {Q: e, g};
  \end{scope}
  % ---------- panel 4: layer 3 discovered ----------
  \begin{scope}[xshift=62mm, yshift=-52mm]
    \node[pl] at (2.2,3.4) {layer 3 discovered};
    \node[Dn] (p4s) at (1.7,2.6) {$s$};
    \node[Dn] (p4a) at (0.6,1.75) {$a$};
    \node[Dn] (p4b) at (1.7,1.75) {$b$};
    \node[Dn] (p4c) at (2.8,1.75) {$c$};
    \node[Dn] (p4e) at (1.7,0.9) {$e$};
    \node[Dn] (p4g) at (2.8,0.9) {$g$};
    \node[Fr] (p4f) at (1.7,0.05) {$f$};
    \node[W] (p4d) at (3.9,1.75) {$d$};
    \draw[ed] (p4s) -- (p4a); \draw[ed] (p4s) -- (p4b); \draw[ed] (p4s) -- (p4c);
    \draw[ed] (p4a) -- (p4b); \draw[ed] (p4b) -- (p4e); \draw[ed] (p4c) -- (p4e);
    \draw[ed] (p4c) -- (p4g); \draw[td] (p4e) -- (p4f); \draw[ed] (p4d) -- (p4c);
    \node[qq] at (2.2,-0.75) {Q: f};
  \end{scope}
\end{tikzpicture}
$$

Vertex $d$ stays white in every panel: no ring ever reaches it. The frontier
never holds vertices from more than two adjacent layers, and once a layer is
fully dequeued the next layer is fully discovered — this is the queue invariant
from the correctness proof, drawn.

**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:

```algorithm
caption: $\textsc{Connected-Components}(G)$ — label every vertex's component
number: 3
$c \gets 0$
foreach vertex $v \in V$ do
  if not $v.visited$ then
    $c \gets c + 1$
    run $\textsc{BFS}(G, v)$, marking each newly visited vertex with $c$
```

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.

::impl{algo="breadth_first_search,traversal_components"}


BFS reads the search skeleton with a queue and exposes shortest hop-distances. Swap the queue for a stack and the same skeleton plunges instead of fanning out, exposing a graph's recursive structure — the timestamps and edge classification that the rest of this module is built on. This continues in [Depth-First Search](/algorithms/graphs/depth-first-search).

[^skiena-graph]: **Skiena**, §5 — Graph Traversal — the hardest part is recognizing a problem as a graph problem.
[^clrs-rep]: **CLRS**, Ch. 22 — Elementary Graph Algorithms — adjacency list versus adjacency matrix and when each is preferred.
[^clrs-bfs]: **CLRS**, Ch. 22 — Elementary Graph Algorithms — BFS computes shortest hop-distances in $O(V + E)$.