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.