1. Depth-First Search

Depth-first search (DFS) explores a graph by going as deeply as possible along each branch before backtracking. From a source vertex it follows an edge to an unvisited neighbour, then an edge from that neighbour, and so on until it reaches a vertex with no unvisited neighbours, at which point it backtracks to the most recent vertex that still has unexplored edges. DFS runs in \(O(V + E)\) and, unlike BFS, uses \(O(V)\) stack depth (recursion stack or explicit stack) rather than \(O(V)\) queue width.

DFS is remarkably versatile: it underpins topological sorting, strongly connected components (Tarjan's / Kosaraju's algorithms), cycle detection, and articulation points / bridges. It is the implicit engine of recursive backtracking algorithms ¹².

1.1 Problem Statement

Given a directed or undirected graph \(G = (V, E)\), a DFS of \(G\) assigns to each vertex \(v\) a discovery time \(d[v]\) and a finish time \(f[v]\) satisfying

This is the parenthesis theorem: the DFS exploration intervals are properly nested.

1.2 The Algorithm

1.2.1 Recursive DFS

DFS(G):
  for each vertex u ∈ V:
    color[u] = WHITE;  π[u] = NIL
  time = 0
  for each vertex u ∈ V:
    if color[u] = WHITE:
      DFS-VISIT(G, u)

DFS-VISIT(G, u):
  time = time + 1
  d[u] = time
  color[u] = GRAY
  for each v ∈ Adj[u]:
    if color[v] = WHITE:
      π[v] = u
      DFS-VISIT(G, v)
  color[u] = BLACK
  time = time + 1
  f[u] = time

1.2.2 Iterative DFS (Explicit Stack)

DFS-ITERATIVE(G, s):
  stack = {s}
  while stack ≠ ∅:
    u = stack.pop()
    if color[u] ≠ BLACK:
      color[u] = BLACK
      for each v ∈ Adj[u] (reversed):
        if color[v] = WHITE:
          stack.push(v)

1.3 Edge Classification

DFS classifies each edge \((u, v)\) by the colours of \(u\) and \(v\) at the moment the edge is first examined:

In an undirected graph, DFS produces only tree edges and back edges.

1.4 Complexity

Space: \(O(V)\) for the colour, timestamp, and predecessor arrays plus \(O(V)\) call stack in the worst case (a path graph).

1.5 Applications

1.5.1 Topological Sort

A topological sort of a directed acyclic graph (DAG) is a linear ordering of vertices such that for every directed edge \((u, v)\), \(u\) appears before \(v\). DFS computes it in \(O(V + E)\): run DFS and insert each vertex at the front of a linked list as it is finished (i.e. as it becomes BLACK). The resulting list is a topological order ¹.

TOPO-SORT(G):
  run DFS(G)
  as each vertex u finishes, insert u at head of list L
  return L

Correctness: if \((u, v) \in E\), then \(f[v] < f[u]\) (because DFS finishes all descendants of \(u\) before \(u\) itself finishes), so \(u\) precedes \(v\) in \(L\).

1.5.2 Cycle Detection

A directed graph contains a cycle if and only if DFS produces a back edge (an edge to a GRAY, i.e. currently-on-stack, vertex). In undirected graphs, any repeated visit via a non-tree edge indicates a cycle.

1.5.3 Strongly Connected Components (Kosaraju's Algorithm)

1. Run DFS on \(G\); record finish times.
2. Transpose \(G\) (reverse all edges) to get \(G^T\).
3. Run DFS on \(G^T\), processing vertices in decreasing finish-time order.
4. Each DFS tree in step 3 is a strongly connected component.

Total cost: \(O(V + E)\) ¹.

1.5.4 Articulation Points and Bridges

An articulation point is a vertex whose removal disconnects the graph. A bridge is an edge whose removal disconnects the graph. Both can be found in \(O(V + E)\) using DFS and the notion of low values (the lowest discovery time reachable from a subtree via at most one back edge).

1.6 Comparison with BFS

1.7 Interactive Demo

The canvas shows DFS on a 7×7 grid from the top-left corner. The algorithm follows one branch as deep as possible (grey cells = on stack, darker = finished). Backtracking is shown when the frontier reverses.