# 5.1 Recursive Depth First Search

Algorithm 4 performs a depth-first search of $G$ rooted at $r$. The counters $dfn$ and $depth$ are global. It relies upon the recursive procedure dfs. Algorithm 5 sketches the implementation of the dfs procedure.

Algorithm 4: Depth First Search
 while next($V$)$\neq finished$ map($\gamma,v,unvisited$) $depth=dfn=0$ dfs($r$)
Algorithm 5: Recursive Depth First Search
 dfs($v$) $dfn=dfn+1$ map($\gamma,v,dfn$) map($\delta,v,depth$) $depth=depth+1$ for all vertices $w$ adjacent to $v$ if evaluate($\gamma,w$) is $unvisited$ map($\rho,w,v$) dfs($w$) $depth=depth-1$

Observe that Algorithm 5 produces three mappings as it performs the DFS: the depth first ordering $\gamma$, the vertex depth map $\delta$, and the predecessor map $\rho$. These mappings provide useful information concerning the structure of the graph. However, only $\gamma$ is actually required by the algorithm. It is initialized with all vertices marked as $unvisited$ and updated as each node is visited.

The time complexity of a depth-first search is linear in the size of $G$, i.e. $O\left(|V|+|E|\right)$. To achieve this linear time complexity, the implementation of the adjacency list is crucial. More specifically, some indication of the most recently visited neighbor (call it vertex $w$) must be maintained for each active vertex $v$. This permits the scan of $v$’s adjacency list to resume at the point where it was suspended when the exploration of $w$ is finished. If you have to rescan the adjacency list of $v$ to pick up where you left off, linearity is lost.