GATE IT 2008 | Question: 47

Question

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)?

• A. $1$ and $3$ only
• B. $2$ and $3$ only
• C. $2, 3$ and $4$ only
• D. $1, 2$ and $3$ only

Answer 1

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.

Comments

Can someone explain in this sequence 

a b e f c g d     after C how g is possible ?

if it is possible only if the sequence would be a b e f c f g d  

---

After c, there are no immediate neighbors to be visited. Hence it backtracks to f. From f, g is visited

---

@shekhar chauhan we can backtrack through visited vertices but not through unvisited vertices so 2 is correct

Answer 2

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      

 

 

Answer 3

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 4

Golden Rule

DFS me agar tum kisi vertex par ho, to jab tak us vertex ke subtree me unvisited vertex available hain, DFS backtrack nahi karega.

 

Option 1: a b e f d g c

Track karo:

a → b → e → f

Ab f ke unvisited neighbours = {c, g}

Lekin sequence bol raha hai next = d.

DFS directly d par jump nahi kar sakta.

Hence, incorrect.

 

Option 2: a b e f c g d

a → b → e → f → c

c ke saare neighbours already visited hain (b,e,f).

Backtrack to f.

Then g.

Then d.

Sab legal hai. Possible

 

Option 3: a d g e b c f

a → d → g → e → b → c

At c, neighbour f unvisited hai.

So next f aa sakta hai.

Possible.

 

Option 4: a d b c g e f

a → d → b → c

At c, unvisited neighbours = {e,f}.

DFS must go to one of them.

But sequence says next = g.

Hence, incorrect.