# 5.4 Depth First Traversal

Following the lead of Horowitz and Sahni (1978) [2], a distinction is made between a depth-first search (Sections 5.1 and 5.2) and a depth-first traversal. Given a graph $G=(V,E)$, a series of depth-first searches that visit all the vertices in $V(G)$ is referred to as a depth-first traversal. If $G$ is a connected graph, a single depth-first search produces a depth-first traversal. Otherwise, a depth-first traversal will discover all of the connected components of $G$.

Algorithm 8 determines a depth-first traversal of $G$. It assumes the buffer $v$ is used to communicate with the vertex list.

Algorithm 8: Depth First Traversal
 $k=$first($V$) while $k\neq eol$ map($\gamma,v,unvisited$) $k=$next($V,k$) $dfn=0$ $k=$first($V$) while $k\neq eol$ if evaluate($\gamma,v$) is $unvisited$ $depth=0$ dfs($v$) $k=$next($V,k$)

The time complexity of a depth-first traversal is linear if dfs is linear.