One more question could be how many 'maximum possible recursion depth' path exists ? :)

Hint - For getting answer quickly partition problem into two sub-problem.

Hint - For getting answer quickly partition problem into two sub-problem.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+24 votes

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

+38 votes

Best answer

Total $21$ nodes are there. $2$ nodes require back track here in this question.

So, max recursion depth is $21-2= 19$

( Do DFS from extreme ends such that max recursion depth will occur i.e. take leftmost top node as initial node for $DFS$ as shown in below image)

Note:- Backtrack means it reduces recursion depth in stack.

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 585
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,126 questions

53,251 answers

184,758 comments

70,502 users