3. Consider the following directed acyclic graph (DAG): A In class, we saw how to use...

Transcribed Image Text:

3. Consider the following directed acyclic graph (DAG): A In class, we saw how to use DFS to find a topological ordering of the the vertices; in the graph above, the unique topological ordering is A, B, C, D, E. We saw an example where we happened to start DFS from the first vertex in the topological order. In this exercise we'll see what happens when we start at a different vertex. Recall that when you run DFS, if it has reach ed everything it can but hasn't yet explored the graph, it will start again at an unexplored vertex. (a) Run DFS starting at vertex C, breaking any ties by alphabetical order.¹ i. What do you get when you order the vertices by ascending start time? ii. What do you get when you order the vertices by descending finish time? (b) Run DFS starting at vertex C, breaking any ties by reverse alphabetical order.² i. What do you get when you order the vertices by ascending start time? ii. What do you get when you order the vertices by descending finish time? [We are expecting: For all four questions, an ordering of vertices. No justification is required.] 3. Consider the following directed acyclic graph (DAG): A In class, we saw how to use DFS to find a topological ordering of the the vertices; in the graph above, the unique topological ordering is A, B, C, D, E. We saw an example where we happened to start DFS from the first vertex in the topological order. In this exercise we'll see what happens when we start at a different vertex. Recall that when you run DFS, if it has reach ed everything it can but hasn't yet explored the graph, it will start again at an unexplored vertex. (a) Run DFS starting at vertex C, breaking any ties by alphabetical order.¹ i. What do you get when you order the vertices by ascending start time? ii. What do you get when you order the vertices by descending finish time? (b) Run DFS starting at vertex C, breaking any ties by reverse alphabetical order.² i. What do you get when you order the vertices by ascending start time? ii. What do you get when you order the vertices by descending finish time? [We are expecting: For all four questions, an ordering of vertices. No justification is required.]

Answer rating: 100% (QA)

a We start DFS at vertex C and break ties in alphabetical ord... View the full answer