## Description

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.

1 2 3

4 5 6

d=

π =

d=

d=

d=

d= d=

π =

π =

π =

π = π =

s

v w

q

t

x

z

r

u

y

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.

m n o p

q r s

t u v w

x y z