An undirected graph G is shown in the figure below.

Assume that the adjacency lists are in alphabetical order. Apply breadth$-$first search $($BFS$)$ on graph G$,$ starting from vertex A$.$

Answer the following questions $($after BFS is completed$).$

$($a$)$ What is the value of C$.$d$?$

$($b$)$ What is the value of J$.$d$?$

$($c$)$ What is the value of C$.$pi$?$

$($d$)$ What is the value of J$.$pi$?$

Preliminaries

We start from a source vertex, s$.$

Discover vertices in the graph

Three possible color values of a vertex

white, not discovered yet

gray, discovered but not explored

black, discovered and explored

Initially, all vertices are white

The source vertex is discovered first

Predecessor$/$Parent

While exploring $($gray$)$ node u$,$ we check the adjacency list u$.$Adj

If v on u$.$Adj is white, we say v is discovered by u$.$ We also say u is the parent or predecessor of v$.$ This is denoted by v$.$pi$=$u

BFS$($G$,$ s$)$

$1$ for each vertex u E G$.$V $-\{$s$\}\{$

$2$ u$.$color $=$ WHITE;

$3$ u$.$d $=+$inf; u$.$pi $=$ NIL;

$4\}$

$5$ s$.$color $=$ GRAY;

$6$ s$.$d $=0$; s$.$pi $=$ NIL

$7$ Q $=$

$8$ Enqueue$($Q$,$ s$)$

$9$ while $($Q$!=)\{$

$10$ u $=$ DEQUEUE$($Q$)$

$11$ for each vertex v E G$.$Adj$[$u$]\{$

$12$ if v$.$color $==$ WHITE$\{$

$13$ v$.$color $=$ GRAY

$14$ v$.$d $=$ u$.$d $+1$

$15$ v$.$pi $=$ u

$16$ Enqueue$($Q$,$ v$)$

$17\}$

$18\}$

$19$ u$.$color $=$ BLACK

$20\}$