Question $1$: DFS and BFS in Graphs $..........................................$ For the following graph problems, design linear time algorithms $($i$.$e$.,$ running time $\backslash ($ O$(|$V$|+|$E$|)\backslash )$ or $\backslash ($ O$($n$+$m$)\backslash )$ as we have been calling it$).$ You should describe each algorithm in English, using around $2-3$ bullets. Do not write code. You can use BFS and DFS as subroutines, without describing them. For each bullet, write down the running time.

In each case, assume that the graph is given to you as an adjacency list.

The goal of this question is for you to learn to think in terms of using standard graph algorithms as "primitives".

For DFS$($u$),$ the output will be a boolean array isReachable$[],$ where isReachable$[$v$]$ is true if $\backslash ($ v $\backslash )$ is reachable from $\backslash ($ u $\backslash )$ via a $($directed$)$ path and false otherwise. For BFS$($u$),$ the output will be an integer array dist $[],$ where dist$[$v$]$ denotes the minimum number of edges in a path from $\backslash ($ u $\backslash )$ to $\backslash ($ v $\backslash ).$ dist $[$v$]$ will be INFINITY if $\backslash ($ v $\backslash )$ is not reachable from $\backslash ($ u $\backslash ).$

$($a$)[5]$ Suppose $\backslash ($ G $\backslash )$ is an undirected graph, and let $\backslash ($ u v $\backslash )$ be an edge in $\backslash ($ G $\backslash ).$ Determine if there is a cycle involving $($i$.$e$.,$ containing$)$ the edge $\backslash ($ u v $\backslash )$ in $\backslash ($ G $\backslash ).$

$($b$)[3]$ Suppose $\backslash ($ G $\backslash )$ is a directed graph and let $\backslash ($ u $\backslash )$ be one of the vertices. Let $\backslash ($ r $\backslash )$ be a given parameter. Determine if exist paths of length $\backslash (\backslash$leq r $\backslash )$ from $\backslash ($ u $\backslash )$ to every other vertex in $\backslash ($ G $\backslash ).$