Depth-First Search: Algorithm

Overview

Depth-First Search (DFS) explores as deeply as possible along each branch before backtracking. It is typically implemented recursively (the call stack acts as the LIFO stack). DFS produces a depth-first forest and assigns two integer timestamps per vertex: discovery time and finish time.

Unlike BFS, DFS does not require a source vertex; it discovers all vertices in the graph by restarting from any unvisited vertex until all have been explored.

Pseudocode

DFS(G):
  for each v in G.V:
    v.colour = WHITE
    v.π = NIL
  time = 0
  for each v in G.V:
    if v.colour == WHITE:
      DFS-VISIT(G, v)

DFS-VISIT(G, u):
  time = time + 1
  u.d = time              // discovery time
  u.colour = GREY
  for each v in G.Adj[u]:
    if v.colour == WHITE:
      v.π = u
      DFS-VISIT(G, v)
  u.colour = BLACK
  time = time + 1
  u.f = time              // finish time

Timestamps

Each vertex gets two timestamps:

• $d[v]$ (discovery time): when the vertex is first encountered (colour changes white → grey).
• $f[v]$ (finish time): when all descendants have been explored (colour changes grey → black).

Timestamps are integers from 1 to $2|V|$. Every vertex is discovered exactly once and finished exactly once.

Worked Example

Consider a directed graph: $V = \{1,2,3,4,5,6,7,8\}$ with edges: $1 \to 2$, $1 \to 3$, $2 \to 3$, $2 \to 4$, $3 \to 5$, $4 \to 5$, $5 \to 6$, $5 \to 8$, $6 \to 7$, $7 \to 6$, $8 \to 4$.

Run DFS starting from vertex 1 (assume adjacency lists in numerical order):

Vertex	1	2	3	4	5	6	7	8
Discover $d$	1	2	3	4	5	6	8	9
Finish $f$	16	15	10	7	12	11	14	13

The timestamps reveal ancestry: vertex 2 is a descendant of 1 because $d[1]=1 < d[2]=2 < f[2]=15 < f[1]=16$.

Parenthesis Theorem

For any two vertices $u$ and $v$, exactly one of the following holds:

1. $[d[u], f[u]]$ and $[d[v], f[v]]$ are disjoint: neither is an ancestor of the other.
2. $[d[u], f[u]]$ is fully contained within $[d[v], f[v]]$: $u$ is a descendant of $v$.
3. $[d[v], f[v]]$ is fully contained within $[d[u], f[u]]$: $v$ is a descendant of $u$.

This theorem implies: $v$ is a proper descendant of $u$ in the depth-first forest iff $d[u] < d[v] < f[v] < f[u]$.

Complexity

$\Theta(|V| + |E|)$ with adjacency lists. Each vertex is discovered once, and the for loop in DFS-VISIT iterates over each adjacency list entry exactly once (or twice for undirected graphs). With an adjacency matrix, the cost becomes $\Theta(|V|^2)$.

DFS Forest

When DFS restarts from an unvisited vertex in the outer loop, it begins a new tree. The set of all trees forms the depth-first forest. For an undirected graph, the number of DFS trees equals the number of connected components.

Comparison: BFS vs DFS

Property	BFS	DFS
Data structure	Queue (FIFO)	Stack (LIFO) / recursion
Source required	Yes ($s$)	No
Distance property	Shortest unweighted paths	Timestamps for ordering
Tree type	Breadth-first tree	Depth-first forest
Edge classification	Not produced	Tree/back/forward/cross
Applications	Shortest paths, bipartite test	Topological sort, SCC, cycle detection

Summary

Aspect	Detail
Traversal order	Deepest-first, then backtracks
Colours	White → Grey → Black
Timestamps	$d[v]$ (discovery), $f[v]$ (finish)
Parenthesis theorem	Intervals are nested or disjoint
Time (adj. lists)	$\Theta(V+E)$
Output	DF forest, timestamps, edge classification

Past paper questions: y2026p1q10 (topological sort via DFS), y2025p1q9(b)(i) (connected components).