(Solved): : Depth First Search (DFS) is a fundamental graph traversal used as building block to solve import ...

: Depth First Search (DFS) is a fundamental graph traversal used as building block to solve important graph problems such as Topological Sort, finding Strongly Connected Components, and others. Hence, the time efficiency of those algorithms depends heavily on implementing efficiently DFS. Given a directed graph $G=\{V,E\}$ encoded as an adjacency list, an efficient implementation of DFS runs in $\underline{O}(/V/+?E?)$ steps. The purpose of this homework is to evaluate experimentally the performance of an efficient implementation of DFS. 1. (50 points) Write a program that, given the adjacency list of a directed graph, computes DFS efficiently. Your program should do the following. (a) Prompt the user to input the number of nodes and the number of edges. (b) Create an adjacency list choosing the edges at random (do not forget that it is a directed graph). (c) Compute DFS (including discovery and finishing times) following the pseudocode in the textbook (attached). (d) Measure and display the running time. 2. (25 points) Using the DFS program of part (1), fill in the following chart with the running times observed for different edge-set sizes. 3. (25 points) Give an approximate formula (with constants, not big-0) for the asymptotic running time of DFS based on your experiments. How does this compare with the expected $\underline{O}?V?+?E?)$ ? If the results differ, overview the code of the data structures used for the adjacency list and explain what might have happened. 4. Extra credit DFS is used as a subroutine for more complex computations in graphs. One of them is Topological Sort. Topological Sort is defined on directed graphs that do not have cycles, customarily called Directed Acyclic Graphs (DAG). If the input graph of Topological Sort is not a DAG, the algorithm returns an incorrect output. So, it is useful to detect cycles to stop the execution in that case. Fortunately, cycles can be detected while running DFS. Your task is to modify the DFS algorithm above to detect cycles. To test your program, write also a method that produces two large directed graphs (try $?\mathrm{V}?>1000$ ), one with cycles and the other without cycles, and runs the cycle detection DFS in both.