classifying graph edges with dfs an execution of depth-first search can be used to analyze the structure of graphbased upon the way in which edges are explored during the traversal the dfs process naturally identifies what is known as the depth-first search tree rooted at starting vertex whenever an edge (uvis used to discover new vertex during the dfs algorithm of code fragment that edge is known as discovery edge or tree edgeas oriented from to all other edges that are considered during the execution of dfs are known as nontree edgeswhich take us to previously visited vertex in the case of an undirected graphwe will find that all nontree edges that are explored connect the current vertex to one that is an ancestor of it in the dfs tree we will call such an edge back edge when performing dfs on directed graphthere are three possible kinds of nontree edgesback edgeswhich connect vertex to an ancestor in the dfs tree forward edgeswhich connect vertex to descendant in the dfs tree cross edgeswhich connect vertex to vertex that is neither its ancestor nor its descendant an example application of the dfs algorithm on directed graph is shown in figure demonstrating each type of nontree edge an example application of the dfs algorithm on an undirected graph is shown in figure bos bos ord ord jfk jfk sfo sfo dfw dfw lax lax mia mia ( (bfigure an example of dfs in directed graphstarting at vertex (bos)(aintermediate stepwherefor the first timea considered edge leads to an already visited vertex (dfw)(bthe completed dfs the tree edges are shown with thick linesthe back edges are shown with dashed linesand the forward and cross edges are shown with dotted lines the order in which the vertices are visited is indicated by label next to each vertex the edge (ord,dfwis back edgebut (dfw,ordis forward edge edge (bos,sfois forward edgeand (sfo,laxis cross edge