Depth first search

Question

The maximum number of edges possible with UDG of n nodes,when DFS call on any random node in the graph result in stack size of 5. i.e. 5 function calls present in stack simultaneously are .........

Ans. 10

Comments

when DFS call on ANY random node in the graph result in stack size of 5

Suppose there is a tree structured graph with height 5. We call DFS on root and the stack size becomes 5. But if we call on any other node we won't get stack size=5. 

To get a stack size=5 on applying DFS to a node, there should be a path from that node which contains 4 other nodes as well. This is because DFS(node) will call each of the other 4 nodes one after the other making stack size = 5 [i.e the starting node + 4 other nodes].

Here we want the same result on applying DFS on any random node so every node should have a path starting from it that contains 4 other nodes.

If you think over it, this can be achieved when the graph is a complete graph with 5 nodes.

A complete graph on 5 nodes will have 10 edges.

---

Brother suppose i have a complete binary tree of height 5 and then when you start a DFS on root it will also contain Stack of size 5 max. Then the max edge is 31.

Am i thinking wrong ?

---

Yes that is what i said that the question says that on applying DFS to ANY node we should get stack size=5. In your case it is just the root node. If you apply on some othernode then you might not get that height. Like suppose you apply DFS on a leaf node then it will call all the nodes upto the root and then again call all the nodes in the other subtree. For complete binary tree DFS(leaf) will give stack size= 9.

---

Oh that means from every node. it will be possible only in case of complete binary tree. Right thanx :)

---

@MiNiPanda, great.... 

But i don't know why add comments instead of answers whenever the question really required

There are so many people, who add answer even the question can clear with a comment, but you are such a guy when there is really need an answer but you make it only comments.

---

Really one of the beautiful question in recent days

---

Shaik Masthan hehe :P :P

---

minipanda what if i take 2 K5 in graph since it is not asking simple connected graph , but you answer assume this .

---

Anu007 Sir though I didn't think it in this way earlier but then we can take infinitely many no. of K5 in the graph to maximize the no. of edges..but the answer should be some finite one..so this assumption can be safely made..Please correct me

---

@Anu007, sir 

in the question they mentioned DFS, if it is really disconnected the term would be replace by DFT