edited by
16,070 views
43 votes
43 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 _________.

edited by

4 Answers

Best answer
69 votes
69 votes

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

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

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

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

edited by
16 votes
16 votes
19. apply DFS.
3 votes
3 votes


Note: We should not consider backtrack edges, it reduces recursion depth in stack.
So the maximum possible recursive depth will be 19.

1 votes
1 votes

Many Would be confused why the recursion depth is not 18 when we have 19 nodes in the recursion call stack, the reason for this is hidden in the definition of recursion depth.

 

Definition of Recursion Depth : The maximum depth of recursion refers to the number of levels of activation of a procedure which exist during the deepest call of the procedure.

 

As we can clearly see that recursion depth is Number of levels not the Height of tree so, answer would be 19 not 18

Answer:

Related questions

49 votes
49 votes
8 answers
1
34 votes
34 votes
4 answers
3
go_editor asked Sep 26, 2014
12,111 views
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjac...