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

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

Algorithm 8: Depth First Traversal
k = k= first( V V )
while  k e o l k\neq eol
   map( γ , v , u n v i s i t e d \gamma,v,unvisited )
    k = k= next( V , k V,k )
d f n = 0 dfn=0
k = k= first( V V )
while  k e o l k\neq eol
   if evaluate( γ , v \gamma,v ) is u n v i s i t e d unvisited
       d e p t h = 0 depth=0
      dfs( v v )
   k = k= next( V , k V,k )

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