Show how depth first search works using figure 22.4 as a guideline for how to show the result of the depth first search. It is only necessary to show the last step. Also, show non-edges, but do not label them as done in that figure (do not label edges as back, cross, or forward edges). Assume that the for loop of lines 5-7 of the DFS procedure considers the vertices in alphabetical order, and assume that each adjacency list is ordered alphabetically. Show the discovery and finishing times for each vertex.

DFS (G) l for each vertex u E G.V 2 u. color WHITE NIL 4 time 5 for each vertex u E G. V Assume thotths considem the if u. color WHITE DFS-VISIT(G. ll white vertex u has just been discovered 1 time time 1 2 u.d time 3 color GRAY 4 for each v e G.Adilu ll explore edge (u, v) if v. color WHITE DFS-VISIT(G, v) ll blacken u: it is finished 8 color BLACK 9 time time 1 10 u f time Figure 22.4 The progress of the depth-first-search algorithm DFS on a directed graph. As edges are explored by the algorithm. they are shown as either shaded (if they are tree edges) or dashed otherwise). Nontree edges are labeled B. C. or F according to whether they are back, cross. or forward edges. Timestamps within vertices indicate discovery timelfinishing times