Please show all work.

(a) (5 points) Say we perform a Depth First Search (DFS), starting with vertex A, on the undirected graph (above left) and count the vertices as we encounter them as described below. Finish filling out the count and previous arrays as determined by our DFS. Assume G.adjacents (v) return vertices adjacent to v in alphabeticumeric order DFSCG, s) t previous count visited for v in G.V A-0 B-1 A=01-1 B-1 C-2 D-3 E-4 F-5 G-6 H-7 visited[y] = false; 8-1 visited[s] = true ; previous[s] =-1; push(s); while stack not empty D-3 E-4 v = pop(); count[y] = n++; for w in G.adjacents(v) F 5 G-6 G-6 H=7 if (!visited[w]) visited[m] = true ; previous w push(w); (b) (3 points) The previous array actually defines a spanning tree constructed by the DFS. Darken the edges are in this tree in the above figure on the left. (c) (5 points) Repeat (a) using the directed graph on the right above. DFSCG, s) previous visited for v in G.V A-01-1 B-1 C-2 D-3 E-4 false; visited[y] n=0 visited[s] true ; previous[s] =-1; push(s); while stack not empty = B-1 C-2 D=3 E=4 F=5 G-6 H=7 C-2 D-3 E-4 v = pop(); count[y] n++ ; for w in G.adjacents ( G-6 H=7 G-6 H=7 if (!visited[w]) visited[n] previousw] true ; push(w); (d) (3 points) Darken the edges of the resulting (directed) spanning tree (rooted at A) encoded in previous