Please read the instructions carefully. You have to use the companion answer sheet (which is a llable PDF le) to type/select your answers to the questions described here. Hand-written assignment (or photo of it) will not be graded. Submit the lled PDF le of the answer sheet on Gradescope, following the link on Canvas. You should name your le using the format CSE310-HW04-LastName-FirstName.pdf. Make sure that your submission can be viewed clearly on gradescope for auto-grading. Adobe Acrobat Reader can be found at https://get.adobe.com/reader/.
Q1 (18 points) A directed graph G is shown in Figure 1. Assume that the adjacency lists are in alphabetical order. Apply depth- rst search (DFS) on graph G. In the main-loop of DFS, check the vertices in alphabetical order.
Figure 1: Graph for Q1.
(a) On the answer sheet, enter the discovery times of selected vertices computed by the DFS.
(b) On the answer sheet, enter the nish times of selected vertices computed by the DFS.
(c) On the answer sheet, enter the predecessors of selected vertices computed by the DFS.
Q2 (6 points) Use the method taught in class to compute the transpose graph GT of G shown in Figure 1. On the answer sheet, answer the questions regarding the adjacency lists of GT .
Q3 (8 points) An undirected graph G is shown in Figure 2. Assume that the adjacency lists are in alphabetical order. Apply breadth- rst search (BFS) on graph G, start from vertex A.
(a) On the answer sheet, answer questions regarding the distance attributes of selected ver-tices computed by the BFS.
(b) On the answer sheet, answer questions regarding the predecessor attributes of selected vertices computed by the BFS.
Figure 2: Graph for Q3.
Q4 (18 points) An undirected graph G is shown in Figure 3. Assume that the adjacency lists are in alphabetical order. Apply depth- rst search (DFS) on graph G. In the main-loop of DFS, check the vertices in alphabetical order.
Figure 3: Graph for Q4.
(a) On the answer sheet, enter the discovery times of selected vertices computed by the DFS.
(b) On the answer sheet, enter the nish times of selected vertices computed by the DFS.
(c) On the answer sheet, enter the predecessors of selected vertices computed by the DFS.
2
