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.

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.