The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
2k views

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 (101k points)
edited by | 2k views
0
One more question could be how many 'maximum possible recursion depth' path exists ? :)

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

how to partition into sub-problem.
0
@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

+30 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 (22.8k points)
edited by
0
U hav solved it after labeling it ... right ??
+15 votes
19. apply DFS.
answered by Boss (19.7k points)
0
why not 20?
+2
and what will be the logic behind that? Actually a vertex will not be visited twice and therefore it is 19
+2
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)


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

39,440 questions
46,623 answers
139,373 comments
57,020 users