1. (15 points) Show d and π values that result from running Breadth First Search on the directed graph below using vertex 3 as the start node.
2. (10 points) Show how Depth First Search works on the graph below by marking on the graph the discovery and finishing times (d and f) for each vertex and the classification of each edge. Assume that the for loops in DFS and DFS-VISIT consider vertices alphabetically.
3. (15 points) List the vertices of the graph below in Topological Order, as produced by the Topological Sort algorithm. Assume that the for loops in DFS and DFS-VISIT consider vertices alphabetically.
4. (15 points) Do Problem 24.1-1 (p. 654) (you do not have to do the last part, i.e., running the algorithm again after changing an edge weight).
5. (15 points) Do Problem 24.2-1 (p. 657). Show the results similar to Fig. 24.5.
6. (20 points) Do Problem 24.3-1 (p. 662).
(7) (10 points) Suppose that a graph G has a Minimum Spanning Tree (MST) computed. How quickly can we update the MST if we add a new vertex and incident edges to G. Propose and outline a strategy and present an algorithm (you can reuse graph algorithms covered in class as building blocks as part of your solution) and evaluate its asymptotic complexity.
