which they are explored during the traversaldistinguishing the edges used to discover new verticescalled discovery edgesor tree edgesfrom those that lead to already visited verticescalled back edges (see figure fin the analogy abovediscovery edges are the edges where we unroll our string when we traverse themand back edges are the edges where we immediately return without unrolling any string as we will seethe discovery edges form spanning tree of the connected component of the starting vertex we call the edges not in this tree "back edgesbecauseassuming that the tree is rooted at the start vertexeach such edge leads back from vertex in this tree to one of its ancestors in the tree the pseudo-code for dfs traversal starting at vertex follows our analogy with string and paint we use recursion to implement the string analogyand we assume that we have mechanism (the paint analogyto determine if vertex or edge has been explored or notand to label the edges as discovery edges or back edges this mechanism will require additional space and may affect the running time of the algorithm pseudo-code description of the recursive dfs algorithm is given in code fragment code fragment the dfs algorithm there are number of observations that we can make about the depth-first search algorithmmany of which derive from the way the dfs algorithm partitions the edges of the undirected graph into two groupsthe discovery edges and the back edges for examplesince back edges always connect vertex to previously visited vertex ueach back edge implies cycle in gconsisting of the discovery edges from to plus the back edge (uvproposition let be an undirected graph on which dfs traversal starting at vertex has been performed then the traversal visits all