GATE CSE 2003 | Question: 21

Question

Consider the following graph: 

Among the following sequences:

1. abeghf
2. abfehg
3. abfhge
4. afghbe

Which are the depth-first traversals of the above graph?

• A. I, II and IV only
• B. I and IV only
• C. II, III and IV only
• D. I, III and IV only

Answer 1

For GATE purpose, without actually applying DFS, we can answer by just seeing options.
In DFS, we go in depth first i.e., one node to another in depth first order.

Here, $abfehg$  is not possible as we can not go from $f$ to $e$ directly.
Thus, option $(D)$ is correct.

In all the other options we can reach directly from the node to the next node.

So, just visualize and do.

Comments

yes but this approach will give u answer in 1 minute

---

Yes. Instead of applying DFS, the best approach for solving questions like this is - trace the traversals given in the options and see whether it can be a depth-first traversal sequence or not.

---

Good shortcut but beware of backtracking, sometimes in gate we can misjudge an option specially now days in msq’s. So if you have time left then always check each option carefully.

Answer 2

Answer will be (D)

DFS goes upto how much depth possible and then backtrack and go to the next link.

Here only 'abfehg' not possible because e and h consecutively is not possible by any backtracking of DFS traversal

Comments

yes, and in DFS just go from root to depth wise how far it can go and then backtrack.

Suppose for tree

      $$A$$

$$|$$

$$------------$$

                                                                            $|$                                                     $|$

                                                                           $B$                                                     $C$

                                                                           $|$

                                                                           $D$

                                                                           $|$

                                                                           $E$

 

Here DFS: A,B,D,E,C

and BFS:A,B,C,D,E

right??

---

yes ma'am. Thank you!

---

can somebody explain option 1, by using stack.

Answer 3

In dfs think of a stack as if every adjacent node is being put on top of it lifo and chosen randomly while in bfs think of a queue i.e.fifo here option d.

Answer 4

Correct Answer : (D)

1. abeghf : Possible $\checkmark$
2. abfehg : After f you can’t go to $e$ before completing $h$ or $g$ $\times$
3. abfhge : Possible $\checkmark$
4. afghbe : Possible $\checkmark$