An undirected graph G is shown in the figure below.

Assume that the adjacency lists are in alphabetical order. Apply depth$-$first search $($DFS$)$ on graph G$.$ In the main loop of DFS$,$ check the vertices in alphabetical order.

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

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

$($b$)$ What is the value of H$.$f$?$

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

$($d$)$ What is the value of I.d$?$

$($e$)$ What is the value of I.f$?$

$($f$)$ What is the value of I.pi$?$

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

$($h$)$ What is the value of J$.$f$?$

$($i$)$ 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

DFS$($G$)$

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

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

$3$ u$.$pi $=$ NIL;

$4\}$

$5$ time $=0$;

$6$ for each vertex U E G$.$V$\{$

$7$ if $($u$.$color $==$ WHITE$)\{$

$8$ DFS$-$Visit$($G$,$ u$)$;

$9\}$;

$10\}$

DFS$-$Visit$($G$,$ u$)$

$1$ time $=$ time $+1$;

$2$ u$.$d $=$ time;

$3$ u$.$color $=$ GRAY;

$4$ for each vertex v E G$.$Adj$[$u$]$

$5$ if $($v$.$color $==$ WHITE$)\{$

$6$ v$.$pi $=$ u

$7$ DFS$-$Visit$($G$,$ v$)$

$8\}$

$9$ time $=$ time $+1$;

$10$ u$.$f $=$ time;

$11$ u$.$color $=$ BLACK;