When searching graphs breadth-first and depth-first color the graph. Who un-colors the graph when the search is completed?

Question

The depth-first and breadth-first algorithms for traversing graphs use a flag (or color) to mark nodes when they are visited. For example some forms of the algorithms use white/grey/black as colors. When the traversal is complete all the nodes in the graph are black.

None of the material I have been reading on these algorithms mentions anything about reverting all the nodes back to white when the traversal is complete.

Are there some extra steps we can add to the algorithms to take care of this? Or must we traverse the graph all over again to reset each node's color? Or perhaps the Graph's data structure is such that changes to the flag/color is temporary and is lost once the traversal is complete?

Answer 1

Your question is, essentiall, "How is this stuff implemented?", to which the answer is "However the implemnter chooses."

Although we talk about nodes of the graph being coloured during the search, implementing that literally as a "visited" field in each node's data record would take up storage space even when no search is in progress. In a concurrent environment, it would also limit you to doing only one search at a time. Instead, it's normal to implement the colouring as a list of visited nodes, or some other structure that is external to the representation of the graph itself; this is typically made explicit in descriptions of, e.g., A* search. This data structure will simply be deallocated when the search is complete.

If you did have an explicit "visited" field in each node then, yes, you'd need to do a separate pass to clear those after each search.

Answer 2

Hi there and happy new year! :)

Colouring vertices is nothing more and nothing less than a didactic resource to explicitly distinguish among three different states:

1. Nodes that have not been visited yet
2. Nodes that have been visited yet not expanded
3. Nodes that have been both visited and expanded

Since the state of a node does not change once a solution has been found, the notion of "de-colouring" the resulting graph is never used.

I think the above fully answers your question but let me please refer to a closely related but somehow different issue: duplicate detection. In spite of using either one strategy or another, it is usually very advantageous to avoid re-expanding nodes when it can be proven that they will not improve the cost of the incumbent solution or that they will not lead to an optimal solution. In the following, I'm covering the basics of mechanisms for duplicate detections under the strategies you mention.

Depth-First Search

When traversing a graph in Depth-First order, the only nodes in memory are those in the path from the root node to the current node. Other nodes previously expanded over which the algorithm backtracked are not in memory any more (and this is indeed the reason why this algorithm takes an amount of memory which is linear in the depth of the search tree!). Thus, the basic mechanism for avoiding duplicate detection is just to compare the child of a newly expanded node with all nodes in the current path from the root node ---just to avoid loops!

Of course, this mechanism could be enhanced by storing all nodes previously expanded but this is not trivial and doing so would lead to a much larger usage of the available memory.

Breadth-First Search

In contraposition to the previous case, Breadth-First Search has a memory consumption which is exponential in the depth of the search tree. Actually, the number of nodes generated dominate the memory consumption. Hence, it is usually a good idea to use an additional data structure to avoid re-expanding nodes. In general, the preferred data structures here are sets or maps where membership operations can be performed in logarithmic time in the number of nodes previously expanded.

Hope this helps,