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