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. 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.¹

What is a graph?

If edges have no direction, so that an edge ${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 = ∣ V ∣$ for the number of vertices and $m = ∣ E ∣$ 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 ${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 $∣ e ∣ = 2$ for every $e \in E \subseteq (2 V)$ ). 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 = {u, v}$ is incident on both, which are its endpoints.
The degree $de g (v) = ∣ {e : e 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 $in-deg (v)$ and $out-deg (v)$ .
The handshake lemma falls straight out of counting incidences both ways: $\sum_{v \in V} de g (v) = 2 ∣ E ∣$ in a graph, and $\sum_{v} in-deg (v) = ∣ E ∣ = \sum_{v} out-deg (v)$ in a digraph.
A walk is an alternating sequence $(v_{0}, e_{1}, v_{1}, e_{2}, \dots, e_{ℓ}, v_{ℓ})$ respecting incidence, of length $ℓ$ . A walk with $v_{0} = v_{ℓ}$ 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:

A small undirected graph on five vertices used throughout the lesson.

A graph is bounded in size: every simple graph has at most $(2 n) = \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 $Θ (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 $Θ (V^{2})$ space regardless of how few edges there are, and listing a vertex's neighbors costs $Θ (V)$ because we must scan a whole row.

Operation	Adjacency list	Adjacency matrix
Space	$Θ (V + E)$	$Θ (V^{2})$
Test edge $(u, v)$ ?	$O (de g u)$	$Θ (1)$
List neighbors of $u$	$Θ (de g u)$	$Θ (V)$
Add an edge	$O (1)$	$Θ (1)$
Iterate over all edges	$Θ (V + E)$	$Θ (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:

The five-vertex graph stored two ways: adjacency lists (left) and the symmetric

0/1

adjacency matrix (right).

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} Θ (1 + de g u) = Θ (V) + Θ (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} Θ (V) = Θ (V^{2})$ no matter how few edges exist. On a sparse graph with $n = 1 0^{6}$ vertices and $m = 3 \times 1 0^{6}$ edges, the list stores about $n + 2 m = 7 \times 1 0^{6}$ entries, while the matrix stores $n^{2} = 1 0^{12}$ cells; a single BFS does $7 \times 1 0^{6}$ units of work versus $1 0^{12}$ . The break-even point sits around $m = Θ (n^{2})$ : only when most possible edges are present does the matrix's $Θ (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.² 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).

adjacency_matrix.pypython

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar

Label = TypeVar("Label", bound=Hashable)

class AdjacencyMatrix(Generic[Label]):
  """
    A graph stored as a dense n*n weight matrix.\n
    Pass `directed=True` for a digraph; otherwise each edge is mirrored\n
    across the diagonal so the matrix stays symmetric.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._index: dict[Label, int] = {}
    self._labels: list[Label] = []
    self._matrix: list[list[float]] = []

  def add_vertex(self, label: Label) -> int:
    """
      Return the row/column index for `label`, creating it if absent.\n
      Growing the matrix appends a fresh zero row and a zero column.\n
    """
    # reuse the existing index when the label is already present.
    existing: Optional[int] = self._index.get(label)
    if existing is not None:
      return existing

    # register the new label at the next index.
    position: int = len(self._labels)
    self._index[label] = position
    self._labels.append(label)

    # widen every existing row, then append the new zero row.
    for row in self._matrix:
      row.append(0.0)
    self._matrix.append([0.0 for _ in range(position + 1)])
    return position

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Stores the weight at the cell; mirrors it when undirected.\n
    """
    # resolve both endpoints, creating them if missing.
    source: int = self.add_vertex(source_label)
    target: int = self.add_vertex(target_label)

    # store the weight, mirroring across the diagonal when undirected.
    self._matrix[source][target] = weight
    if not self.directed:
      self._matrix[target][source] = weight

  def has_edge(self, source_label: Label, target_label: Label) -> bool:
    """
      Whether an edge runs from `source_label` to `target_label` — O(1).\n
    """
    # missing endpoints mean no edge.
    source: Optional[int] = self._index.get(source_label)
    target: Optional[int] = self._index.get(target_label)
    if source is None or target is None:
      return False

    return self._matrix[source][target] != 0.0

  def weight(self, source_label: Label, target_label: Label) -> float:
    """
      The stored weight of the edge, or 0 when no edge exists.\n
    """
    # missing endpoints carry no weight.
    source: Optional[int] = self._index.get(source_label)
    target: Optional[int] = self._index.get(target_label)
    if source is None or target is None:
      return 0.0

    return self._matrix[source][target]

  def neighbors(self, label: Label) -> list[Label]:
    """
      Every vertex reachable from `label` by one edge — scans a row, O(V).\n
    """
    # scan the row and collect every column holding a non-zero weight.
    source: int = self._index[label]
    return [
      self._labels[target]
      for target, cell in enumerate(self._matrix[source])
      if cell != 0.0
    ]

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._labels)

  def matrix(self) -> list[list[float]]:
    """
      A copy of the underlying n*n weight grid.\n
    """
    return [row[:] for row in self._matrix]

  def __contains__(self, label: Label) -> bool:
    return label in self._index

  def __iter__(self) -> Iterator[Label]:
    return iter(self._labels)

  def __len__(self) -> int:
    return len(self._labels)

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

\textsc{Whatever-First-Search}(G, s)

— the generic skeleton

1
foreach vertex $v \in V$ do
2
$v.visited \gets \text{false}$
3
$v.\pi \gets \text{nil}$
4
$s.visited \gets \text{true}$
5
put $s$ into the bag $B$
6
while $B \neq \emptyset$ do
7
take a vertex $u$ out of $B$
bag decides who
8
foreach $v$ adjacent to $u$ do
9
if not $v.visited$ then
10
$v.visited \gets \text{true}$
11
$v.\pi \gets u$
12
put $v$ into the bag $B$

The $π$ 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	$BFS$ — explores in rings
Stack (LIFO)	newest first	$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 of later lessons are just Whatever-First-Search with a priority queue. Everything below specializes this one skeleton.

whatever_first_search.pypython

from collections import deque
from collections.abc import Hashable
from typing import Generic, Optional, Protocol, TypeVar

from graph import Graph

Label = TypeVar("Label", bound=Hashable)

class Bag(Protocol[Label]):
  """
    The frontier container: the discipline behind it picks the next vertex.\n
  """

  def push(self, label: Label) -> None: ...

  def pop(self) -> Label: ...

  def __len__(self) -> int: ...

class QueueBag(Generic[Label]):
  """
    A FIFO bag (oldest out first) — instantiates the skeleton as BFS.\n
  """

  def __init__(self) -> None:
    self._items: deque[Label] = deque()

  def push(self, label: Label) -> None:
    self._items.append(label)

  def pop(self) -> Label:
    return self._items.popleft()

  def __len__(self) -> int:
    return len(self._items)

class StackBag(Generic[Label]):
  """
    A LIFO bag (newest out first) — instantiates the skeleton as DFS.\n
  """

  def __init__(self) -> None:
    self._items: list[Label] = []

  def push(self, label: Label) -> None:
    self._items.append(label)

  def pop(self) -> Label:
    return self._items.pop()

  def __len__(self) -> int:
    return len(self._items)

def whatever_first_search(
  graph: Graph[Label],
  source: Label,
  bag: Bag[Label],
) -> dict[Label, Optional[Label]]:
  """
    Explore everything reachable from `source`, using `bag` to decide order.\n
    Returns the predecessor map of the search tree: each visited vertex maps\n
    to the vertex it was discovered from (the source maps to None).\n
  """
  # seed the frontier with the source.
  predecessor: dict[Label, Optional[Label]] = {source: None}
  visited: set[Label] = {source}
  bag.push(source)

  while len(bag) > 0:
    # pull the next vertex the bag's discipline hands back.
    current: Label = bag.pop()

    for edge in graph.vertex(current).outgoing:
      # discover each undiscovered neighbor and push it onto the frontier.
      neighbor: Label = edge.target.label
      if neighbor not in visited:
        visited.add(neighbor)
        predecessor[neighbor] = current
        bag.push(neighbor)

  return predecessor

graph.pypython

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

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.

Same graph, same source: the queue (BFS) builds a shallow bushy tree, the stack (DFS) a deep spine.

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 . π$ , the vertex from which $v$ was discovered. The predecessors form the breadth-first tree (or shortest-path tree) ${(v . π, v) : v 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 2:

\textsc{BFS}(G, s)

— shortest distances in hops from

s

1
foreach vertex $u \in V \setminus \set{s}$ do
2
$u.color \gets \text{white}$
3
$u.d \gets \infty$
4
$u.\pi \gets \text{nil}$
5
$s.color \gets \text{gray}$
discover source
6
$s.d \gets 0$
7
$s.\pi \gets \text{nil}$
8
$Q \gets \emptyset$
9
enqueue $(Q, s)$
10
while $Q \neq \emptyset$ do
11
$u \gets$ dequeue $(Q)$
12
foreach $v$ adjacent to $u$ do
13
if $v.color = \text{white}$ then
first time reaching v
14
$v.color \gets \text{gray}$
15
$v.d \gets u.d + 1$
16
$v.\pi \gets u$
17
enqueue $(Q, v)$
18
$u.color \gets \text{black}$
19
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.

Proof. Collect the vertices into layers $L_{k} = {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 $π$ 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} = {s}$ with $s . d = 0$ . For the step, let $v \in L_{k + 1}$ . Some shortest path $s ⇝ 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 . π$ satisfies $v . π . d = v . d - 1$ , so following $π$ 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. $□$

Running time. Initialization touches every vertex once: $Θ (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 $Θ (E)$ total. Hence BFS runs in $O (V + E)$ , linear in the size of the graph.³

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

s \to a, s \to b, s \to c, a \to b, b \to e, c \to e, c \to g, e \to f, 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 . π$ )	Queue after
— (init)	—	$s . d = 0$	$⟨ s ⟩$
$s$	$a, b, c$	$a . d = 1$ , $b . d = 1$ , $c . d = 1$ , all $π = s$	$⟨ a, b, c ⟩$
$a$	$b$	none ( $b$ gray)	$⟨ b, c ⟩$
$b$	$e$	$e . d = 2$ , $e . π = b$	$⟨ c, e ⟩$
$c$	$e, g$	$g . d = 2$ , $g . π = c$ ( $e$ gray)	$⟨ e, g ⟩$
$e$	$f$	$f . d = 3$ , $f . π = e$	$⟨ g, f ⟩$
$g$	—	none	$⟨ f ⟩$
$f$	—	none	$⟨ ⟩$

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

BFS tree from

s

with vertices sorted into distance layers

d = 0

3

Thick edges are tree edges $(v . π, 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:

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.

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

\textsc{Connected-Components}(G)

— label every vertex's component

1
$c \gets 0$
2
foreach vertex $v \in V$ do
3
if not $v.visited$ then
4
$c \gets c + 1$
5
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.

breadth_first_search.pypython

from collections import deque
from collections.abc import Hashable
from typing import Generic, NamedTuple, Optional, TypeVar

from graph import Graph

Label = TypeVar("Label", bound=Hashable)

class BFSResult(NamedTuple, Generic[Label]):
  """
    The output of a BFS run: hop-distances and the predecessor tree.\n
    A vertex absent from `distance` is unreachable from the source.\n
  """
  distance: dict[Label, int]
  predecessor: dict[Label, Optional[Label]]

def breadth_first_search(
  graph: Graph[Label], source: Label
) -> BFSResult[Label]:
  """
    Shortest hop-distances from `source` to every reachable vertex.\n
    `distance[source]` is 0 and each neighbor is one greater than its\n
    discoverer; `predecessor` traces a shortest path back to the source.\n
  """
  # source sits at distance 0 and roots the tree.
  distance: dict[Label, int] = {source: 0}
  predecessor: dict[Label, Optional[Label]] = {source: None}
  frontier: deque[Label] = deque([source])

  while frontier:
    # expand the oldest vertex, then its undiscovered neighbors one ring out.
    current: Label = frontier.popleft()
    for edge in graph.vertex(current).outgoing:
      neighbor: Label = edge.target.label
      if neighbor not in distance:  # first time reaching the neighbor
        distance[neighbor] = distance[current] + 1
        predecessor[neighbor] = current
        frontier.append(neighbor)

  return BFSResult(distance, predecessor)

def shortest_path(
  graph: Graph[Label],
  source: Label,
  target: Label,
) -> Optional[list[Label]]:
  """
    A fewest-edge path from `source` to `target`, or None if unreachable.\n
    Walks the BFS predecessor pointers back from the target and reverses.\n
  """
  # unreachable target has no predecessor entry.
  result: BFSResult[Label] = breadth_first_search(graph, source)
  if target not in result.predecessor:
    return None

  # walk predecessors from the target back to the source.
  path: list[Label] = []
  step: Optional[Label] = target
  while step is not None:
    path.append(step)
    step = result.predecessor[step]

  # reverse into source-to-target order.
  path.reverse()
  return path

traversal_components.pypython

from collections import deque
from collections.abc import Hashable
from typing import TypeVar

from graph import Graph

Label = TypeVar("Label", bound=Hashable)

def connected_components(graph: Graph[Label]) -> dict[Hashable, int]:
  """
    Map every vertex to its component number (counting from 0).\n
    Two vertices share a number iff a path joins them. Intended for\n
    undirected graphs; on a digraph it labels weakly-reachable sets from\n
    each unvisited start in insertion order.\n
  """
  component: dict[Hashable, int] = {}
  next_label: int = 0

  for start in graph.vertices:
    # skip starts already swept into an earlier component.
    if start.label in component:
      continue

    # open a fresh component and seed its traversal frontier.
    component[start.label] = next_label
    frontier: deque[Label] = deque([start.label])

    while frontier:
      # tag every vertex this sweep reaches with the current label.
      current: Label = frontier.popleft()
      for edge in graph.vertex(current).outgoing:
        neighbor: Label = edge.target.label
        if neighbor not in component:
          component[neighbor] = next_label
          frontier.append(neighbor)

    next_label += 1

  return component

def count_components(graph: Graph[Label]) -> int:
  """
    The number of connected components in the graph.\n
  """
  if len(graph) == 0:
    return 0
  return max(connected_components(graph).values()) + 1

graph.pypython

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

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.

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

What is a graph?

Two ways to store a graph

One traversal to rule them all

Breadth-first search

Footnotes