5.2 Non-recursive Depth First Search

Since the procedure described in Section 5.1 has a depth of recursion of V|V| in the worst case, Algorithm 5 may have unacceptable execution characteristics (such as stack overflow) for large graphs. Algorithm 6 removes the recursion from the dfs function.

Algorithm 6: Depth First Search With Recursion Removed
dfs(rr)
   visit(r,noparentr,noparent)
   v=rv=r
   next edge
   for all vertices ww adjacent to vv
      if evaluate(γ,w\gamma,w) is unvisitedunvisited
         depth=depth+1depth=depth+1
         visit(w,vw,v)
         v=wv=w
   goto next edge
   if vrv\neq r
      v=v=evaluate(ρ,v\rho,v)
      depth=depth-1depth=depth-1
      goto next edge

The vertex visitation procedure visit is straightforward and is specified in Algorithm 7.

Algorithm 7: Non-recursive DFS Vertex Visitation
visit(v,predecessorv,predecessor)
   map(δ,v,depth\delta,v,depth)
   map(ρ,v,predecessor\rho,v,predecessor)
   dfn=dfn+1dfn=dfn+1
   map(γ,v,dfn\gamma,v,dfn)

Observe that vertex visitation (Algorithm 7) generates the three mappings (γ\gamma, δ\delta, and ρ\rho) that were produced by the recursive procedure. Note that the predecessor mapping ρ\rho is required by the unwound dfs procedure. It was not required by the recursive implementation since equivalent information is implicitly retained on the stack during recursion.

The computational complexity of this unwound procedure is similar to that of the recursive implementation.

When implementing non-recursive depth first search, don’t forget that the dfs function of Algorithm 6 is imbedded in the overall procedure defined by Algorithm 4.

See Sections and 5.1 for more information on these issues.