GATE CSE 2014 | Set 3 | Question: 13

Question

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

Comments

https://youtu.be/ZPNwt6SUvr8?t=3704

---

one possible order below answer 19 vertices only 2 vertices are remainng(Red one) 

---

Many student confuse that why not consider Backtrack....bcoz " Backtracking decreases the tree/search depth"

Answer 1

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.

Comments

The min depth should be 7 rt?.

as @Abhrajyoti00 bhaiya mentioned above :https://gateoverflow.in/?qa=blob&qa_blobid=13103728789498995128

here just start with the middle and go towards left and after finishing left we would be left with only 1 rec call i.e. the initial rec call and then go towards right and in the right, first go upwards till 8th rec call and come back which will leave us with 5 rec calls and then go downwards which will go upto 7 rec calls atmax. So I think the min rec call would be 7.

---

note : here calculating recursive depth with respect to number of vertices but not number of edges

---

I am also thinking the same....can some clarify about minimum depth?

Answer 2

19. apply DFS.

Comments

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)

---

Because we have to count vertices not edges so 19 not 20

Answer 3

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

Comments

thankyou

Answer 4

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

Answer 5

The best answer is enough so here I m just posting about the difference between tree depth & recursion depth

1. Tree/Graph Depth

When we say a node is at depth 4 from root:

A → B → C → D → E

Depth of E = 4 edges

because

depth=#edges from root

---

2. Recursion Depth

Suppose DFS does:

DFS(A)
  DFS(B)
    DFS(C)
      DFS(D)
        DFS(E)

At the deepest point, stack contains:

A
B
C
D
E

That's 5 function calls.

So recursion depth = 5, not 4.

---

Relationship

For a simple chain:

A → B → C → D → E

• Number of edges = 4
• Number of vertices = 5
• Recursion depth = 5

Hence:

Recursion Depth=Path Length (edges)+1