When do you add a node to visited in bfs or dfs?

Question

Hey I've been researching BFS/DFS and I noticed that many of them have a slight modification and that is when a node is added to the visited set.

In one way, the algorithm would pop the node from the stack/queue and then add it to the visited set. It will then add all the neighbors that haven't been visited

In another implementation, the node isn't added to the visited set there. Instead it will add all the neighbors that haven't been visited to the stack/queue, but it would add those neighbors to the visited set the moment it is added to the stack/queue.

So to summarize, in one method they are added to the visited set when they are popped out to the stack/queue. In another method they are added to the visited set when they are added to the stack/queue.

My two questions are these: What is the difference between the two? Which one should I use?

I can see somewhat of a problem happening if I only add it to the visited when it is popped and there are cycles in the graph, but I'm not 100% sure about that either. Any help would be greatly appreciated.

user_1925388 · Answer

Both are having the same algorithmic complexity and correctness.

However, marking a vertex visited only before starting to traverse the neighbours is slightly slower. In case of BFS, it means adding the same vertex to the queue multiple times redundantly. In case of DFS, it means calling the dfs function on the same vertex multiple times redundantly.

Hence, I personally always like to mark a vertex as visited before adding it to stack/queue.

When do you add a node to visited in bfs or dfs?

1 Answers