Question: (a) (15 pts) Do a DFS starting at C, assuming vertices are to be considered in alphabetical order. Show discovery and finish times near
(a) (15 pts) Do a DFS starting at C, assuming vertices are to be considered in alphabetical order. Show discovery and finish times near each vertex, separated by a comma. Classify edges as tree edges, back edges, forward edge, cross edge. E B H F (b) (10 pts) Use the DFS in part (a) to do a topological sort on this graph. Draw the resulting graph with vertices on a line, i.e. list the vertices in topologically-sorted order. (c) (10 pts) Using inspection, identify the strongly connected components. If we reverse the direction of the edges from D to A and E to D, what are the strongly connected components?
Step by Step Solution
There are 3 Steps involved in it
a DFS starting at C assuming vertices are to be considered in alphabetical order Edge classification ... View full answer
Get step-by-step solutions from verified subject matter experts
