The adjacency list representation of a graph G, which has 7 vertices and 10 edges, is:

(a)Show the breadth-first search tree that is built by running BFS on graph G with the given adjacency list, using vertex a as the source.

(b)Indicate the edges in G that are NOT in the BFS tree in part (a) by dashed lines.

(c)Show the depth-first search tree that is built by running DFS on graph G with the given adjacency list, using vertex a as the source.

(d)Indicate the edges in G which are NOT in the DFS (c) by dashed lines.
 

Transcribed Image Text:

g a → d, e, b, g cf, e, b, d ea, c, b ga b→ e, c, a d→ c, a, f fd, c d a e b C g a → d, e, b, g cf, e, b, d ea, c, b ga b→ e, c, a d→ c, a, f fd, c d a e b C

Answer rating: 100% (QA)

To answer this question we need to follow these steps 1 Construct the adjacency list representation ... View the full answer