Given the following directed graph: B G A Perform a Depth-First Search (DFS) on the given...

Transcribed Image Text:

Given the following directed graph: B G A Perform a Depth-First Search (DFS) on the given graph, using vertex G as the source. (a) Suppose that neighbors of a vertex is accessed in alphabetical order. List the vertices in the discovered order of DFS and show for each vertex v, its discovery time d[v] and finish time f[v]. [14] (b) Draw the depth-first tree obtained. [6] [10] (c) Show the classification of each edge (tree edge, back edge, forward edge, cross edge). (d) Does the graph has a topological sort? Justify your answer. [5] Given the following directed graph: B G A Perform a Depth-First Search (DFS) on the given graph, using vertex G as the source. (a) Suppose that neighbors of a vertex is accessed in alphabetical order. List the vertices in the discovered order of DFS and show for each vertex v, its discovery time d[v] and finish time f[v]. [14] (b) Draw the depth-first tree obtained. [6] [10] (c) Show the classification of each edge (tree edge, back edge, forward edge, cross edge). (d) Does the graph has a topological sort? Justify your answer. [5]