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,EG=(V,E), a series of depth-first searches that visit all the vertices in VGV(G) is referred to as a depth-first traversal. If GG 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 GG.

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

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

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