Algorithms Homework

Problems 1. Traversal Applications. a.) (10 points) Modify the Depth-first Search (DFS) algorithm so that it can detect whether a cycle in any given directed unweighted graph G = (V, E). You can start with the DFS pseudocode in the slides and create a new modified version DFS_CYC(V,E) that takes as input the graph and returns TRUE if there is a cycle or FALSE otherwise. What is the running time of your algorithm? b.) (10 points) Modify the Breadth-first Search (BFS) algorithm so that it can count the number of connected components in any given undirected unweighted grap G = (V, E). You can start with the BFS pseudocode in the slides and create a new modified version BFS_COMP(V,E) that takes as input the graph and returns the number of connected components. What is the running time of your algorithm? c.) (5 points) Determine which of the following algorithms: BFS, DFS, Prims algorithm, is the asymptotically fastest when you want to find the minimum spanning tree in an unweighted undirected graph G = (V, E). Justify your