The Gateway to Computer Science Excellence
+2 votes
156 views
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
in DS by Loyal (7k points) | 156 views
+5

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.

0
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 ?
+1

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
Oh that means from every node. it will be possible only in case of complete binary tree. Right thanx :)
0

@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
Really one of the beautiful question in recent days
0

Shaik Masthan hehe :P :P

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

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

@Anu007, sir 

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

Please log in or register to answer this question.

Related questions

+2 votes
0 answers
2
asked Jan 25, 2018 in DS by budhu (139 points) | 120 views
0 votes
0 answers
3
asked Nov 7, 2018 in Programming by Na462 Loyal (7k points) | 189 views
+1 vote
1 answer
4
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
198,046 comments
104,671 users