1) (6 points, 3 points each): Breadth-First Search allows us to determine the distance from a vertex s (start) to all other vertexes in an Undirected Graph. (The BFS algorithm also works for a Directed Graph.) The version of the algorithm in CLRS in Section 22.2 (page 595 of the Third Edition) labels each vertex v with its parent on a shortest path to get from vertex s to vertex v. In the CLRS algorithm, .d is v's distance from s, and . is v's parent on the shortest path from s to V. Also, WHITE means Unvisited, GRAY means InProgress, and BLACK means AllDone. For example, in the graph on Slide 66 of Lecture 16, the parent of B is A, the parent of G is C, and the parent of D is E. a) Describe an algorithm that takes an Undirected Graph G and 2 vertices s and v as inputs, and prints out a shortest path going from s to v in G. Use pseudocode or English (not C), but your algorithm should be clear and efficient. b) What is the complexity of your algorithm for finding the shortest path from s to v? Give an answer involving n (number of vertices in G) and m (number of edges in G) that will be good even if the graph is sparse. Having an inefficient algorithm for part a) will lose points for part b). 1) (6 points, 3 points each): Breadth-First Search allows us to determine the distance from a vertex s (start) to all other vertexes in an Undirected Graph. (The BFS algorithm also works for a Directed Graph.) The version of the algorithm in CLRS in Section 22.2 (page 595 of the Third Edition) labels each vertex v with its parent on a shortest path to get from vertex s to vertex v. In the CLRS algorithm, .d is v's distance from s, and . is v's parent on the shortest path from s to V. Also, WHITE means Unvisited, GRAY means InProgress, and BLACK means AllDone. For example, in the graph on Slide 66 of Lecture 16, the parent of B is A, the parent of G is C, and the parent of D is E. a) Describe an algorithm that takes an Undirected Graph G and 2 vertices s and v as inputs, and prints out a shortest path going from s to v in G. Use pseudocode or English (not C), but your algorithm should be clear and efficient. b) What is the complexity of your algorithm for finding the shortest path from s to v? Give an answer involving n (number of vertices in G) and m (number of edges in G) that will be good even if the graph is sparse. Having an inefficient algorithm for part a) will lose points for part b)