The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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 _________.

asked in Algorithms by Veteran (115k points)
edited by | 2.6k views
One more question could be how many 'maximum possible recursion depth' path exists ? :)

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

how to partition into sub-problem.
@chhotu either give whole solution( atleast someone catch your point) or dont give any these type  of hint ,one downvote for this comment

2 Answers

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

answered by Boss (23.6k points)
edited by
U hav solved it after labeling it ... right ??
Wouldn't the maximum recursion depth be "n-1''? So, 18 ?
+15 votes
19. apply DFS.
answered by Boss (19.9k points)
why not 20?
and what will be the logic behind that? Actually a vertex will not be visited twice and therefore it is 19
A better approach should be to count the number of nodes, and eliminate those nodes which form, say a radical(nodes which can terminate the link), and those that may end up (the DFS link) into a cycle.

(Pardon for using non standard terms)

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,126 questions
53,251 answers
70,502 users