Q1. Consider the following DFS algorithm for cycle detection in a graph.
DFS(G)
for each vertex u Belongs G.V
u.color = WHITE
U.pi = NIL
time = 0
for each vertex u Belongs G.V
if u.color == WHITE
DFS-VISIT(G , u)
DFS-VISIT(G, u)
time = time + 1
u.d = time
u.color = GRAY
for each v Belongs G.Adj[u]
if (v.color == GRAY AND v.d + 1 < u.d) // cycle detection Mechanism
CYCLE DETECTED
if(v.color == WHITE)
v.pi = u
DFS-VISIT( G, v)
u.color = BLACK
time = time + 1
u.f = time
Above Algorithm will detect the cycle in the graph - [True / False].
If your answer is false, then provide a counter case.
Q2. Cross edge can never be found in given Graph, but after getting DFS tree if we draw an edge from one leaf node to another leaf node then that edge is called cross edge.
Is this statement is true ??