retagged by
7,824 views
23 votes
23 votes

Consider the following sequence of nodes for the undirected graph given below:

  1. $a$ $b$ $e$ $f$ $d$ $g$ $c$
  2. $a$ $b$ $e$ $f$ $c$ $g$ $d$
  3. $a$ $d$ $g$ $e$ $b$ $c$ $f$
  4. $a$ $d$ $b$ $c$ $g$ $e$ $f$

A Depth First Search (DFS) is started at node $a$. The nodes are listed in the order they are first visited. Which of the above is/are possible output(s)?

  1. $1$ and $3$ only
  2. $2$ and $3$ only
  3. $2, 3$ and $4$ only
  4. $1, 2$ and $3$ only
retagged by

3 Answers

Best answer
25 votes
25 votes

Answer: B
1. After $f$ is visited, $c$ or $g$ should be visited next. So, the traversal is incorrect.
4. After $c$ is visited, $e$ or $f$ should be visited next. So, the traversal is incorrect.
$2$ and $3$ are correct.

edited by
2 votes
2 votes

Answer is B.

1. Visit a then b then e then f then we can't go back to d because we have a chance to go c or g which are still not visited so so abefdgc is wrong.      

2. Visit a then b then e then f then c now all the path adjacent to c is already covered so we have to backtrack to f then go to g then d

3. Similarly a then d then g then e then b then c then f can be visited.

4. But a,d then b is not possible because we can't go back to a then b because there are nodes adjacent to explore so this is wrong      

 

 

0 votes
0 votes

I) After visiting 'f', 'c' or 'g' should be visited next. So, the traversal is incorrect.
IV) After visiting 'c', 'e' or 'f' should be visited next. So, the traversal is incorrect.

Answer:

Related questions

1 votes
1 votes
4 answers
3