The Gateway to Computer Science Excellence
+17 votes
2k views

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?

  1. I, II and IV only
  2. I and IV only
  3. II, III and IV only
  4. I, III and IV only
in Algorithms by Veteran (52.2k points)
edited by | 2k views

3 Answers

+19 votes
Best answer
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.
by Loyal (9.5k points)
edited by
0
I am nt getting wat u said ... u hav solved it without using stack ???
+3
keep moving from the root vertex like- moving from root to any of the child node, then from the child node to any of its child node and backtrack only when u have exhausted all the child nodes of the current node, in this manner if u can visit all the nodes its a successful DFS. If in the option like option b here, you happen to backtrack before exhausting all the child nodes of the current node, it is not a successful DFS.
0
Technically u r imagining a stack ... right ??
+1
yes but this approach will give u answer in 1 minute
+1
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.
+7 votes

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

by Veteran (119k points)
0

@srestha mam, using stack i am getting only 4th one as valid depth first traversal. Because, an elemant is first popped out and then its adjacent elements are pushed onto stack. Can you please show using stack how 1 and 3 are also possible?

0
Then can u show me, how u got 4th one??
0

@srestha mam, here i have attached scanned image pdf

+1
I think , what u have applied is BFS concept actually.

In DFS, we go , how much distance we can cover and then backtrack. But in BFS , we check child of each node and then push and pop accordingly
0
yes, i pushed all the children of node as soon as i popped it and combined bfs with stack. Really sorry for this silly mistake!
+1
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??
+1
yes ma'am. Thank you!
+5 votes
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.
by Active (3.3k points)
Answer:

Related questions

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
50,737 questions
57,392 answers
198,593 comments
105,444 users