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

edited | 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

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.

edited
0
U hav solved it after labeling it ... right ??
19. apply DFS.
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)