DFS(G) 1 for each vertex u E G. #2 (8 pts) DFS and Cycles DFS classifies edges in directed graphs as tree edges, back edges, forward edges, and cross edges (see p. 609) Undirected graphs do not have forward or cross edges .colorWHITE time 0 5 for each vertex E G. if 11.color wHITE DFS-VISIT(G,u) (a) (2 pts) How can you modify DFS to detect back-edges? Say how you would modify the DFS and/or DFS-Visit procedures to print out all back edges found (reference CLRS line numbers to state your solution clearly). Then explain why your solution leads to the correct result. DFS-VISIT(G,u) 1 time-time +1 3 u.coorGRAY 4 for each v E G.Ad[u] if v.colorWHITE DFS-VISIT(G, v) 8 . color= BLACK (b) (2 pts) How can you modify DFS to determine whether a graph (directed or undirected) has a cycle? Say how you would 10 /-time the DFS and/or DFS-Visit modify procedures to print something and exit (return) when a cycle is found (reference CLRS line numbers to state your solution clearly). Then explain why your solution leads to the correct result. (c) (2 pts) What is the asymptotic run time of your cycle-detection algorithm in (b) on directed graphs? Assume that it exits the DFS as soon as a cycle is found. Justify your answer (d) (2 pts) What is the asymptotic run time of your cycle-detection algorithm in (b) on undirected graphs? Assume that it exits the DFS as soon as a cycle is found. Justify your