How do you best mark node as visited in Depth First Search?

In some algorithms, like DFS, we need to mark nodes as visited. If I have a Node class, in Python we can write something like node.visited = True. However when I do that, I change the nodes which might be undesired. So what would be the best and cleanest approach here? Things I thought of:

• delete the attribute at the end of the algorithm for each node if the attribute exists for that node (might increase complexity if we didn’t have to loop through all nodes in the first instance)
• create copies of all instances (a lot of overhead)
• create a Hash table and look up the attribute there.

Answer

You could use a set, which is in essence the hash table solution already implemented in the standard library. Sets allow you to test if the node was visited using the in operator in constant time:

>>> visited = set()
>>> visited.add(node)
>>> node in visited
True

You can store the node directly if it provides a __hash__() method, otherwise you’ll need a hashable unique identifier instead.