5.2 Non-recursive Depth First Search

Since the procedure described in Section 5.1 has a depth of recursion of $|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.

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

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.