5.1 Recursive Depth First Search

Algorithm 4 performs a depth-first search of GG rooted at rr. The counters dfndfn and depthdepth 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(VV)finished\neq finished
   map(γ,v,unvisited\gamma,v,unvisited)
depth=dfn=0depth=dfn=0
dfs(rr)
Algorithm 5: Recursive Depth First Search
dfs(vv)
   dfn=dfn+1dfn=dfn+1
   map(γ,v,dfn\gamma,v,dfn)
   map(δ,v,depth\delta,v,depth)
   depth=depth+1depth=depth+1
   for all vertices ww adjacent to vv
      if evaluate(γ,w\gamma,w) is unvisitedunvisited
         map(ρ,w,v\rho,w,v)
         dfs(ww)
   depth=depth-1depth=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 unvisitedunvisited and updated as each node is visited.

The time complexity of a depth-first search is linear in the size of GG, i.e. OV+EO\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 ww) must be maintained for each active vertex vv. This permits the scan of vv’s adjacency list to resume at the point where it was suspended when the exploration of ww is finished. If you have to rescan the adjacency list of vv to pick up where you left off, linearity is lost.