(10%) Trace the run of Depth-First search (DFS) algorithm starting from v in the graph below....

Transcribed Image Text:

(10%) Trace the run of Depth-First search (DFS) algorithm starting from v in the graph below. For tracing, use the same notation as in the class notes and HW3 solutions. In case of multiple options follow numerical order. The answer should start with: Check v1 edge v1-v2 Mark an near the edges that participate in the final tree. Notice that even though it looks a bit like the graph from HW3, it's not the exact same graph. (b) (10%) This graph is a DAG. provide a topological sorting of the vertices in the grap Use any algorithm mentioned in the class or HW. State which algorithm you used and outline it briefly. If you use the reverse postorder you may just refer to your results for part (a). (c) (5%) Does the graph have more than one topological sort? If so- find at least i another topological sort, different than (b). Otherwise, explain (Hint: HW). (10%) Trace the run of Depth-First search (DFS) algorithm starting from v in the graph below. For tracing, use the same notation as in the class notes and HW3 solutions. In case of multiple options follow numerical order. The answer should start with: Check v1 edge v1-v2 Mark an near the edges that participate in the final tree. Notice that even though it looks a bit like the graph from HW3, it's not the exact same graph. (b) (10%) This graph is a DAG. provide a topological sorting of the vertices in the grap Use any algorithm mentioned in the class or HW. State which algorithm you used and outline it briefly. If you use the reverse postorder you may just refer to your results for part (a). (c) (5%) Does the graph have more than one topological sort? If so- find at least i another topological sort, different than (b). Otherwise, explain (Hint: HW).

Answer rating: 100% (QA)

a Check v1 edge v1v2 Mark v1 Check v2 edge v2v3 Mark v2 Check v3 edge v3v4 Mark v3 Check v... View the full answer