Description
1. What is the running time of DFS if the graph is given as an adjacency list and adjacency matrix? Justify
your running time.
2. Run DFS on the graph below, assume that DFS considers vertices in alphabetical order and the adjacency
lists are also alphabetical order. Show the discover times and finishing times of each vertex in the graph.
3. Write a method that takes any two nodes π’ and π£ in a tree π, and quickly determines if the node π’ in the
tree is a πππ πππππππ‘ or πππππ π‘ππ of node π£
4. Draw the parenthesis structure of the dfs of Figure 1 (start from u, assume that DFS considers vertices in
alphabetical order) and see the example parenthesis structure as Figure 2.
Figure 1 Figure 2