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
