0
$\begingroup$

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


How graph edges can be converted to a function call ? Is that mean here we have to do a recursive call. I am not getting clear, what is function call here. Plz help

$\endgroup$
  • $\begingroup$ If you want the question clarified, you should ask the person who set it. $\endgroup$ – David Richerby Apr 30 at 10:13
  • $\begingroup$ No, I want to clear the concept to attempt such question . I really do mistake in such mathematical calculative question. It is a online test question. $\endgroup$ – Srestha Apr 30 at 10:18
2
$\begingroup$

Graph edges are not "converted to function calls". DFS is a recursive function. When you call DFS on some start node, it looks at the adjacent vertices (vertices which are connected to this node via an edge) and recursively calls itself on one of them.
But since each node is only visited once in a DFS, the maximum stack size cannot be greater than the number of nodes.

$\endgroup$
  • $\begingroup$ And what is answer here? $\endgroup$ – Srestha Apr 30 at 10:21
  • $\begingroup$ Here since maximum number of edges are present, it means it's a fully connected graph. Let's say the vertices are numbered from 1 to 5. And the initial call is dfs(1). Then the stack will contain: dfs(5), dfs(4), dfs(3), dfs(2), dfs(1) in this order $\endgroup$ – AKai Apr 30 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.