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 graph 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, Prim's algorithm, is the asymptotically fastest when you want to find the minimum spanning tree in an unweighted undirected graph G = (V, E). Justify your answer. Recall that a connected component is a (sub)-set of vertices that can all reach each other via some path. 1 Computer Engineering Department Kuwait University 2. Shortest Path. (20 points) You are given the following directed weighted graph G = (V, E): 5 11 U2 -2 6 Vo 8 -3 7 2 9 U3 V4 (a) (10 points) Use the Bellman-Ford algorithm to determine the shortest path from node vo to every other node. You may use any ordering of the edges. Show all your work including the distance values at the end of every pass. (b) (8 points) Apply Dijkstra's algorithm on graph G with the source vertex as vo. Show all your work. (c) (2 points) State whether the shortest path from vo to vi that you obtained in part (b) is the same as part (a). Explain your answer. 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 graph 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, Prim's algorithm, is the asymptotically fastest when you want to find the minimum spanning tree in an unweighted undirected graph G = (V, E). Justify your answer. Recall that a connected component is a (sub)-set of vertices that can all reach each other via some path. 1 Computer Engineering Department Kuwait University 2. Shortest Path. (20 points) You are given the following directed weighted graph G = (V, E): 5 11 U2 -2 6 Vo 8 -3 7 2 9 U3 V4 (a) (10 points) Use the Bellman-Ford algorithm to determine the shortest path from node vo to every other node. You may use any ordering of the edges. Show all your work including the distance values at the end of every pass. (b) (8 points) Apply Dijkstra's algorithm on graph G with the source vertex as vo. Show all your work. (c) (2 points) State whether the shortest path from vo to vi that you obtained in part (b) is the same as part (a). Explain your