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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+15 votes

Consider the following graph:

Among the following sequences:

- abeghf
- abfehg
- abfhge
- afghbe

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

- I, II and IV only
- I and IV only
- II, III and IV only
- I, III and IV only

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

+2

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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,855 questions

47,520 answers

145,896 comments

62,278 users