I am nt getting wat u said ... u hav solved it without using stack ???

The Gateway to Computer Science Excellence

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

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.

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

+7 votes

Answer will be (D)

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

Here only 'abf**eh**g' not possible because e and h consecutively is not possible by any backtracking of DFS traversal

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?

+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

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!

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,392 answers

198,593 comments

105,444 users