3. Do a DFS on the following directed graph with the ordering A, B, C, D,...

 

Transcribed Image Text:

3. Do a DFS on the following directed graph with the ordering A, B, C, D, E, F, G, H, I, J, K, L. In other words, if there is a choice between vertices to pick, pick the one that is first alphabetically. a. List the edges in the order marked and draw the DFS tree on the graph. b. Show arrival/departure times on the vertices. c. Determine if it's possible to do a topological ordering of the graph. If so, do the topological ordering including all edges. If not possible, explain. d. Classify the edges into tree, forward, back and cross edges. A E B L G M H 3. Do a DFS on the following directed graph with the ordering A, B, C, D, E, F, G, H, I, J, K, L. In other words, if there is a choice between vertices to pick, pick the one that is first alphabetically. a. List the edges in the order marked and draw the DFS tree on the graph. b. Show arrival/departure times on the vertices. c. Determine if it's possible to do a topological ordering of the graph. If so, do the topological ordering including all edges. If not possible, explain. d. Classify the edges into tree, forward, back and cross edges. A E B L G M H