0
$\begingroup$

Is there a way in which Depth First Traversal will put a node into the stack more than once using the general algorithm as shown here.

Also, is it compulsory for all nodes to be entered into the stack atleast once? Is there any case in which a node is not entered into the stack?

$\endgroup$

closed as off-topic by Christian Clason, nicoguaro, Paul Jan 13 '17 at 22:42

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ At least when I have implemented DFT algorithms for graphs, there's usually a Boolean variable for each node denoting if it's been seen or not. If it hasn't been seen before, it gets added to the stack. If it has been seen, it gets ignored. If you are aiming to traverse the whole graph, then each node should be put on the stack once. For approximation algorithms though, only a subset of the nodes may end up getting put on the stack. $\endgroup$ – spektr Jan 12 '17 at 16:49
  • $\begingroup$ Ya, ideally we always have a boolean array for visited. However this question has been asked multiple times and there was no answer as 'all nodes once in stack'. Couldn't find it on net either. $\endgroup$ – Pepper Jan 12 '17 at 16:57
  • $\begingroup$ The Boolean array for checking if things are visited keeps nodes from being added to the stack more than once, so the answer to your first question is No. Now DFT should pass through each node on the graph as long as there exists a path from any one node to another. Since DFT should pass through each node, it means it should end up on the stack at least once. Since we know it can't be added on more than once but should end up on the stack at least once, we can conclude each node will end up on the stack exactly once for a nominal DFT. $\endgroup$ – spektr Jan 12 '17 at 17:19
3
$\begingroup$

Depth first search will put a node into the stack only once. The usual way to perform DFS involves marking a vertex as marked while pushing it into the stack and not pushing an already marked vertex again.

A node will not enter the stack if and only if it is not part of the connected component involving the DFS start vertex. This only matters for graphs made out of disjoint connected components and not for connected graphs.

$\endgroup$

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