Depth-First Search

This builds on Graph Representations and Traversal, which set up graphs, the two representations, and the $\text{Whatever-First-Search}$ skeleton read with a queue as breadth-first search. Here we read the same skeleton with a stack, and the change of order exposes an entirely different structure.

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

from collections.abc import Hashable
from enum import Enum
from typing import NamedTuple, Optional, TypeVar

from graph import Graph

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

WHITE: int = 0  # undiscovered
GRAY: int = 1  # discovered, still on the recursion stack
BLACK: int = 2  # finished, all descendants done

class EdgeKind(Enum):
  """
    The four DFS edge classes, decided by the far endpoint's color.\n
  """
  TREE = "tree"
  BACK = "back"
  FORWARD = "forward"
  CROSS = "cross"

class DFSResult(NamedTuple):
  """
    The output of a full DFS sweep over the graph.\n
    `discovery` / `finish` hold each vertex's timestamps; `predecessor`\n
    is the depth-first forest; `edge_kinds` classifies every edge.\n
  """
  discovery: dict[Hashable, int]
  finish: dict[Hashable, int]
  predecessor: dict[Hashable, Optional[Hashable]]
  edge_kinds: dict[tuple[Hashable, Hashable], EdgeKind]

def depth_first_search(graph: Graph[Label]) -> DFSResult:
  """
    Run DFS over the whole graph, restarting from any leftover white\n
    vertex so disconnected pieces are covered too (a depth-first forest).\n
    Vertices are visited in insertion order; ties broken the same way.\n
  """
  # every vertex starts white; the rest of the state fills in as we go.
  color: dict[Hashable, int] = {
    vertex.label: WHITE for vertex in graph.vertices
  }
  discovery: dict[Hashable, int] = {}
  finish: dict[Hashable, int] = {}
  predecessor: dict[Hashable, Optional[Hashable]] = {}
  edge_kinds: dict[tuple[Hashable, Hashable], EdgeKind] = {}
  clock: int = 0

  def visit(label: Label) -> None:
    nonlocal clock

    # stamp the discovery time and turn the vertex gray.
    clock += 1
    discovery[label] = clock
    color[label] = GRAY

    for edge in graph.vertex(label).outgoing:
      # classify the edge by the far endpoint's color, recursing on tree edges.
      neighbor: Label = edge.target.label
      key: tuple[Hashable, Hashable] = (label, neighbor)
      if color[neighbor] == WHITE:
        edge_kinds[key] = EdgeKind.TREE
        predecessor[neighbor] = label
        visit(neighbor)
      elif color[neighbor] == GRAY:
        # neighbor is an ancestor still on the stack.
        edge_kinds[key] = EdgeKind.BACK
      elif discovery[label] < discovery[neighbor]:
        # finished descendant reached by a non-tree edge.
        edge_kinds[key] = EdgeKind.FORWARD
      else:
        edge_kinds[key] = EdgeKind.CROSS

    # finish the vertex: turn it black and stamp the finish time.
    color[label] = BLACK
    clock += 1
    finish[label] = clock

  # restart from any leftover white vertex to cover disconnected pieces.
  for vertex in graph.vertices:
    if color[vertex.label] == WHITE:
      predecessor[vertex.label] = None
      visit(vertex.label)

  return DFSResult(discovery, finish, predecessor, edge_kinds)

def has_cycle(graph: Graph[Label]) -> bool:
  """
    Whether the graph contains a cycle.\n
    A digraph is cyclic iff DFS finds a back edge. For an undirected\n
    graph the same test applies, ignoring the trivial back edge straight\n
    to a vertex's own parent (the mirror of the tree edge just taken).\n
  """
  # a back edge witnesses a cycle, except the parent-mirror in an undirected graph.
  result: DFSResult = depth_first_search(graph)
  for (source, target), kind in result.edge_kinds.items():
    if kind is EdgeKind.BACK:
      if not graph.directed and result.predecessor.get(source) == target:
        continue  # the reverse of the tree edge, not a real cycle
      return True

  return False

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)

A worked DFS, and the parenthesis structure

Run $\text{DFS}$ on the digraph below. The outer loop scans vertices in the order $s,w,y,x,z,t,q,r$, and each adjacency list is scanned alphabetically. The clock ticks once per stamp:

• $t=1$: discover $s$. Its list is $w,z$; the first neighbor $w$ is white.
• $t=2$: discover $w$ (so $w.\pi =s$). Its list is $y,z$; $y$ is white.
• $t=3$: discover $y$. Its only neighbor $x$ is white.
• $t=4$: discover $x$. No white neighbors.
• $t=5$: finish $x$. $t=6$: finish $y$ — back in $w$, whose next neighbor $z$ is still white.
• $t=7$: discover $z$. Its list is $s,x$: $s$ is gray (an active ancestor), $x$ is black — neither is entered, but both edges get classified below.
• $t=8$: finish $z$. $t=9$: finish $w$ — back in $s$, whose remaining neighbor $z$ is now black.
• $t=10$: finish $s$. The outer loop resumes and finds $t$ still white.
• $t=11$: discover $t$; $t=12$/$13$: discover and finish $q$; $t=14$/$15$: discover and finish $r$ (its neighbor $q$ is black); $t=16$: finish $t$.

Each vertex below is labeled with its interval as discovery/finish. Thick edges are tree edges (the depth-first forest — two trees here, rooted at $s$ and $t$); dashed edges are the non-tree edges, tagged B (back), F (forward), or C (cross) and classified in the next section.

The discovery and finish times nest like balanced parentheses. Write each vertex's interval $[s_v,f_v]$. Reading the trace above as brackets — open at discovery, close at finish — gives

a well-formed string: intervals can never partially overlap. This is the parenthesis theorem (Erickson calls it the nesting lemma).¹

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.

This is the cleanest test for what will end up under $u$.

This makes look for a back edge a decision test for cyclicity, and the two clauses are precisely its soundness and completeness. Every back edge lies on a cycle is soundness: when DFS flags a back edge, a genuine cycle is there — no false alarm. Every cycle contains a back edge is completeness: no cycle slips past the search. Together they underlie 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).

The color test runs during the traversal; once DFS finishes, the timestamps alone decide, courtesy of the parenthesis theorem. For an edge $(u,v)$:

(Tree and forward edges share the interval pattern — $v$ a descendant of $u$ — and are told apart by $v.\pi =u$.) The fourth conceivable pattern, $s_u<s_v$ with $v$ finishing after $u$, never occurs for an edge: if $v$ is discovered while $u$ is active, the white-path property pulls $v$ into $u$'s subtree, so $v$ finishes first. A minimal example exhibiting all four classes:

DFS from $u$ walks the chain $u,v,w$; the edge $w\to u$ finds $u$ gray (back), and on the way out $u\to w$ finds $w$ black inside $u$'s interval (forward). The restart at $x$ finds $w$ black with $f_w<s_x$ (cross).

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.

Worked example: connected components

The outer driver — restarting DFS from any leftover white vertex — labels connected components for free. Each restart begins a new tree, and every vertex it reaches shares the same component. Take an undirected graph on seven vertices with edges $a$–$b$, $b$–$c$, $a$–$c$ (a triangle), the lone edge $d$–$e$, and the isolated pair $f$–$g$. Scanning vertices alphabetically:

• Restart 1 at $a$ (component $1$). DFS visits $a$, then $b$, then $c$; from $c$ the edge $c$–$a$ finds $a$ gray, a back edge that closes the triangle but visits nothing new. Component $1=\left\{a,b,c\right\}$.
• Restart 2 at $d$ (component $2$). DFS visits $d$, then $e$ across the single edge; $e$ has no other neighbor. Component $2=\left\{d,e\right\}$.
• Restart 3 at $f$ (component $3$). DFS visits $f$, then $g$. Component $3=\left\{f,g\right\}$.

Three restarts, three components. The number of times the outer loop calls $\text{DFS-Visit}$ from a white vertex is the number of connected components, computed in the same $\Theta (V+E)$ pass — no extra structure needed beyond a component counter incremented at each restart.

The dashed edge $c$–$a$ is the triangle's one back edge; every other edge is a tree edge, matching the undirected rule above. On a directed graph the same restart-counting overcounts — reachability is one-way — the gap that strongly connected components close with a second DFS pass.

Common pitfalls

Traversal code is short, and most of its bugs hide in the two lines everyone writes from memory.

• Marking visited at dequeue instead of enqueue. If BFS checks the color only when a vertex leaves the queue, a vertex can be enqueued once per incoming edge before its first copy is processed. Distances still come out right (the first copy dequeued carries the smallest $d$), but the queue swells to $\Theta (E)$ entries. Discover-time marking — gray the vertex the moment it is first seen — is what keeps each vertex enqueued once true.
• No visited check at all. On any graph with a cycle the traversal loops forever; on a dense DAG it can revisit vertices exponentially often. The visited flag is the entire difference between graph search and blind walking.
• Undirected graphs stored one-way. An undirected edge $\left\{u,v\right\}$ must appear on both adjacency lists. Insert only $(u,v)$ and the graph silently becomes a digraph; BFS distances and connectivity both come out wrong, and nothing crashes to tell you.
• Recursive DFS on deep graphs. A path of $10^6$ vertices means recursion depth $10^6$, which overflows the call stack in most language runtimes long before memory runs out. Production DFS either raises the recursion limit or maintains an explicit stack of (vertex, position-in-adjacency-list) frames — and the naive push all neighbors stack version visits vertices in a valid DFS order but does not reproduce the recursive discovery/finish times, so timestamp-based arguments quietly break.
• Parent edges masquerading as cycles. In an undirected graph, DFS from $v$ immediately re-sees the edge back to its parent $v.\pi$, which is gray. That is not a cycle; cycle detection must ignore the single edge to the parent (and be careful again if parallel edges are allowed).
• Trusting vertex order. Adjacency-list order changes the BFS tie-breaking order within a layer and the shape of the DFS forest. Distances and the parenthesis structure are guaranteed; which shortest-path tree or which edge classification you get is not, so tests that hard-code one particular tree are brittle.

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

What DFS unlocks

Almost every algorithm in the rest of this module is DFS with a small amount of bookkeeping added. The timestamps and the edge classification are the raw material.

Cycle detection, traced. The cycle theorem (acyclic iff no back edge) is a decision procedure. Take the dependency graph $a\to b\to c\to a$ with a side branch $b\to d$. DFS from $a$ discovers $a$ (gray), then $b$ (gray), then $c$ (gray); $c$'s only edge is $c\to a$, and $a$ is gray — an ancestor still on the recursion stack — so $c\to a$ is a back edge and a cycle is reported the instant it is scanned. The gray set at that moment, $\{a,b,c\}$, holds exactly the cycle's vertices. Contrast a graph with $c\to d$ instead of $c\to a$: every scanned edge lands on a white or black vertex, DFS finds no back edge, and the finish order $d,c,b,a$ (reverse of finishing) is a valid topological order.

Iterative DFS. The recursive form is the clearest, but a path of a million vertices overflows the call stack in most runtimes. The fix is an explicit stack of frames — a (vertex, iterator-into-its-adjacency-list) pair — so the recursion lives on the heap. The subtlety worth flagging: the naive push all neighbors at once stack does visit vertices in a valid DFS order, but it does not reproduce the discovery/finish timestamps, because a vertex can be pushed several times before it is first popped. Any argument that leans on the parenthesis structure (edge classification, low-link values) needs the frame-based iterative form that stamps finish times on the way back down the stack.

The rest of the module, in one sentence each. Every algorithm ahead is DFS plus a specific piece of bookkeeping:

• Topological sort and SCC orders a DAG by reverse finish time, and finds strongly connected components by running DFS twice (Kosaraju) or tracking low-links in one pass (Tarjan).
• Bridges and articulation points add a low[v] value — the earliest discovery time reachable from $v$'s subtree via one back edge — to find the edges and vertices whose removal disconnects the graph.
• Lowest common ancestor and Eulerian tours both walk the DFS tree, one reading its ancestor structure, the other its edge traversal order.

DFS is a framework: run the depth-first walk, and decide what to record. The choice of bookkeeping is the design space.

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 (parenthesis + white-path theorems) and classify edges; 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.