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

while next($V$)$\neq finished$ |

map($\gamma,v,unvisited$) |

$depth=dfn=0$ |

dfs($r$) |

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.