3 votes 3 votes 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 DS depth-first-search data-structures graph-algorithm + – Na462 asked Aug 21, 2018 Na462 1.3k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply MiNiPanda commented Aug 21, 2018 reply Follow Share 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. 6 votes 6 votes Na462 commented Aug 21, 2018 reply Follow Share 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 ? 0 votes 0 votes MiNiPanda commented Aug 21, 2018 reply Follow Share 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. 1 votes 1 votes Na462 commented Aug 21, 2018 reply Follow Share Oh that means from every node. it will be possible only in case of complete binary tree. Right thanx :) 1 votes 1 votes Shaik Masthan commented Aug 21, 2018 reply Follow Share @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. 0 votes 0 votes Shaik Masthan commented Aug 21, 2018 reply Follow Share Really one of the beautiful question in recent days 0 votes 0 votes MiNiPanda commented Aug 21, 2018 reply Follow Share Shaik Masthan hehe :P :P 0 votes 0 votes Anu007 commented Aug 21, 2018 reply Follow Share minipanda what if i take 2 K5 in graph since it is not asking simple connected graph , but you answer assume this . 0 votes 0 votes MiNiPanda commented Aug 21, 2018 reply Follow Share 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 0 votes 0 votes Shaik Masthan commented Aug 21, 2018 reply Follow Share @Anu007, sir in the question they mentioned DFS, if it is really disconnected the term would be replace by DFT 0 votes 0 votes Please log in or register to add a comment.