# Can a Depth first traversal of a graph visit node more than once? [closed]

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?

• 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. Jan 12, 2017 at 16:49
• 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. Jan 12, 2017 at 16:57
• 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. Jan 12, 2017 at 17:19