Question $2$: Consider the following directed graph:

$(2\mathrm{.}1)$ Draw the $DFS-$forest obtained by running algorithm DFS$.$ Classify each edge as a tree edge, forward edge, back edge, or cross edge. In the DFS$-$forest, give the pre$-$ and post$-$number of each vertex. Whenever there is a choice of vertices, pick the one that is alphabetically first.

$(2\mathrm{.}2)$ Draw the $DFS-$forest obtained by running algorithm DFS$.$ Classify each edge as a tree edge, forward edge, back edge, or cross edge. In the DFS$-$forest, give the pre$-$ and post$-$number of each vertex. Whenever there is a choice of vertices, pick the one that is alphabetically last.

Note that in $(2\mathrm{.}1)$ algorithm DFS$($G$)$ starts by calling Explore$($A$),$ Explore for vertex A$.$

Note that in $(2\mathrm{.}2)$ algorithm DFS$($G$)$ starts by calling Explore$($G$),$ Explore for vertex $G.$

Algorithm DFS $(G)$ :

for each vertex $v$

do visited$(v)=$ false

endfor;

clock $=1$;

for each vertex $v$

do if visited$(v)=$ false

then ExPLORE$(v)$

endif

endfor

Algorithm Explore $(v)$ :

visited$(v)=$ true;

pre $(v)=$ clock;

clock $=$ clock $+1$ ;

for each edge $(v,u)$

do if visited $(u)=$ false

then EXPLORE $(u)$

endif

endfor;

post$(v)=$ clock;

clock $=$ clock $+1$

Question $2$: Consider the following directed graph:

$(2\mathrm{.}1)$ Draw the $DFS-$forest obtained by running algorithm DFS$.$ Classify each edge as a tree edge, forward edge, back edge, or cross edge. In the DFS$-$forest, give the pre$-$ and post$-$number of each vertex. Whenever there is a choice of vertices, pick the one that is alphabetically first.

$(2\mathrm{.}2)$ Draw the $DFS-$forest obtained by running algorithm DFS$.$ Classify each edge as a tree edge, forward edge, back edge, or cross edge. In the DFS$-$forest, give the pre$-$ and post$-$number of each vertex. Whenever there is a choice of vertices, pick the one that is alphabetically last.

Note that in $(2\mathrm{.}1)$ algorithm DFS$($G$)$ starts by calling Explore$($A$),$ Explore for vertex A$.$

Note that in $(2\mathrm{.}2)$ algorithm DFS$($G$)$ starts by calling Explore$($G$),$ Explore for vertex G$.$

Algorithm $DFS(G)$ :

for each vertex $v$

do visited$(v)=$ false

endfor;

clock $=1$;

for each vertex $v$

do if visited$(v)=$ false

then ExPLORE$(v)$

endif

endfor

Algorithm EXPLORE $(v)$ :

visited$(v)=$ true;

pre$(v)=$ clock;

clock $=$ clock $+1$ ;

for each edge $(v,u)$

do if visited $(u)=$ false

then ExplorE$(u)$

endif

endfor;

post$(v)=$ clock;

clock $=$ clock $+1$