Awesome q2a theme
0 votes

Why b option is incorrect


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

ago in DS by (13 points) | 23 views

1 Answer

+1 vote
Best answer

If a node v in DFS is visited after another node u then:

  • Either the node v is directly adjacent of the node u and u-v edge exists
  • Or u has no new unvisited nodes as adjaceny nodes and DFS backtracks to another unvisited node of any previous node and u-v doesn't exist.

Consider this simple graph


    /     \

2          3

If we start DFS from 1, the nodes would be traversed as 1-2-3 and 2-3 edge doesn't exist.

ago by (2.9k points)
selected ago by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,968 questions
3,119 answers
95,792 users