Description
EL 9343 Homework 8
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
