2022-149

Given the following directed graph, if DFS is started from vertex 0 for an implementation in which the adjacency lists are in sorted order, then what is correct to affirm regarding edge classifications:

A. {a, b, c, d} are tree-edges; 

    {g, h} are forward-edges;

    {e, f} are back-edges;

    {i} is a cross-edge

B. {b, e, d, i, j, c} are tree-edges; 

     {g} is a forward-edge; 

     {a} is a back-edge; 

     {h} is a cross-edge;

C. {a, b, c, g} are tree-edges; 

    {d, h} are forward-edges;

    {e, f} are back-edges;

    {i} is a cross-edge;

D. {a, b, c, d} are tree-edges; 

    {g, h} are forward-edges;

    {e, i} are back-edges;

    {f} is a cross-edge

E. None of the above

Original idea by: Marcelo Silva