
1.6. CYCLE-BASED ALGORITHMS 11
Figure 1.4 A DFS traversal of a graph. Thick lines re pr e se nt the tree edges, while the
back edges are drawn with dashed li ne s. Each vertex is identified wit h its D F S in de x.
The edges by which DFS discovers new vertices of G form a spanning tree T of G, called
Palm Tree, or DFS Tree. The root of T is the vertex at which the traversal started. The
edges of T are called tree edges, while the remaining edges of G are called back edges (or
co-tree edges).
After performing a DF S traversal, each vertex v of G can be associated with a DFS index ,
DFS(v), that is , the order in which v was reached during ...