Algorithm DFS(G): for each vertex v do visited(v) = false endfor; clock = 1; for each vertex v do if visited(v) = false then Explore(v) endif endfor

Algorithm Explore(v): visited(v) = true; pre(v) = clock; clock = clock + 1; for each edge (v; u) do if visited(u) = false then Explore(u) endif endfor; post(v) = clock; clock = clock + 1

Question 3: Consider the following directed graph: A B E D F G . 1 1 (3.1) Draw the DFS-forest obtained by running algorithm DFS; the pseudocode is at the end of this assignment. Algorithm DFS uses algorithm EXPLORE as a subroutine. The pseudocode for this subroutine is also given at the end of this assignment. Classify each edge as a tree edge, forward edge, back edge, or cross edge. In the DFS- forest, give the pre- and post-number of each vertex. Whenever there is a choice of vertices, pick the one that is alphabetically first. (3.2) Draw the DFS-forest obtained by running algorithm DFS. Classify each edge as a tree edge, forward edge, back edge, or cross edge. In the DFS-forest, give the pre- and post-number of each vertex. Whenever there is a choice of vertices, pick the one that is alphabetically last