Problem $2.$ Depth$-$First Search $(10$ points$)$

$($a$)$ Draw an example of a directed graph $G$ including vertices $s,u,$ and $v$ such that:

There is a path from $u$ to $v$ in $G,$ and

There is a DFS traversal starting from $s$ such that $u$ is discovered before $v$ but $v$ is not a

descendant of $u$ in the DFS tree.

$($You can assume that ties are broken in alphabetical or numeric order.$)$

Solution:

$($b$)$ Show the $v.s$ and $v.$f time of every vertex $v$ when we run Depth$-$First Search on your graph

$G$ starting at vertex $s.$

Solution:

$($c$)$ Can your DFS results be used to topologically$-$sort the vertices of your graph? If so$,$ give the

topological order. If not, explain why.

Solution:

$($d$)$ Classify each edge of your graph as a tree edge, back edge, forward edge, or cross edge.

Solution: