GATE Exam | Aptitude Questions | GATE Syllabus | GATE Result | Mock Test | GATE Preparation
0 votes

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

A

{u,v} must be an edge in G, and u is a descendant of v in T

B

{u,v} must be an edge in G, and v is a descendant of u in T

C

If {u,v} is not an edge in G then u is a leaf in T

D

If {u,v} is not an edge in G then u and v must have the same parent in T

asked in trees, binary search trees, binary heaps by gate

1 Answer

0 votes
If {u,v} is not an edge in G then u is a leaf in T
answered by gate

Related questions

The best answer to any question