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. 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.

---

very easy method is just go edge by edge u cant go back once you visited that node then that is dfs

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$

Answer 5

We will go systematically and explore each vertices and it’s neighbors and will backtrack where possible. Let’s start-

1. abeghf

   

   

   

   

   

   2. abfehg
      This is not possible as after exploring $f$ we will have unvisited vertices $h$,$g$ as neighbours, but $e$ can’t come.
   3. abfhge
       ​​​​​
   4. afghbe

$Ans: D$

Answer 6

According to definition of DFS the path is explored until dead end but in option B it explores upto f only it possible explore dead end but it backtracks to again 'a' it violates definition of DFS.