reachable from the starting dfs on digraph vertex into tree edges or discovery edgeswhich lead us to discover new vertexand nontree edgeswhich take us to previously visited vertex the tree edges form tree rooted at the starting vertexcalled the depth-first search treeand there are three kinds of nontree edgesback edgeswhich connect vertex to an ancestor in the dfs tree forward edgeswhich connect vertex to descendent in the dfs tree cross edgeswhich connect vertex to vertex that is neither its ancestor nor its descendent refer back to figure to see an example of each type of nontree edge proposition let be digraph depth-first search on starting at vertex visits all the vertices of that are reachable from alsothe dfs tree contains directed paths from to every vertex reachable from visited by dfs starting justificationlet be the subset of vertices of at vertex we want to show that contains and every vertex reachable from belongs to suppose nowfor the sake of contradictionthat there is vertex reachable from that is not in consider directed path from to wand let (uvbe the first edge on such path taking us out of that isu is in but is not in when dfs reaches uit explores all the outgoing edges of uand thus must reach also vertex via edge ( ,vhencev should be in and we have obtained contradiction thereforev must contain every vertex reachable from analyzing the running time of the directed dfs method is analogous to that for its undirected counterpart in particulara recursive call is made for each vertex exactly