Please show all work.

(a) (5 points) Say we perform a Breadth First Search (BFS), 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 BFS. Assume G.adjacents(v) return vertices adjacent to v in alphabeticumeric order BFS(G, s) count previous visited for v in G.V A-0 A-01-1 B-1 visited[v] false; n=0 visited[s] true; previous [s] 1 enqueue(s); while stack not empty t B-1 C-2 D-3 E-4 D-3 E-4 v dequeue) count[y] = n++; for w in G.adjacents(v G-6 G-6 if (lvisited[w]) f visited[m] = true ; previous[w] = v; enqueue(w); 31 (b) (3 points) Darken the edges that are in the resulting spanning tree constructed by the BFS in the above figure on the left (c) (5 points) Repeat (a) using the directed graph on the right above BFSCG, s) i previous visited count for v in G.V A 0 8-1 A=01-1 visited[y] = false; B-1 visited[s] = true; previous[s] 1; enqueue(s); while stack not empty D-3 D-3 E=4 v = dequeue(); count[y] = n++; for w in G.adjacents(v) G-6 G-6 if (!visited[w]) visited[w] = true ; previous[m] =v; enqueue(w); (d) (3 points) Darken the edges of the resulting (directed) spanning tree (rooted at A) encoded in previous