What's the good of using 3 states for a vertex in DFS?

Question

In the explanation of depth-first search (DFS) in Algorithms in a Nutshell (2nd edition), the author used 3 states for a vertex, say white(not visited), gray(has unvisited neighbors), black(visited).

Two states (white and black) are enough for a traverse. Why add the gray state? What's it used for?

Answer 1

This is a variation of the DFS algorithm shown in Introduction to Algorithms by Coerman at al.

When you use 3 colors instead of only 2, it gives you more information. Fist, it allows you at each point during the algorithm run, to know which vertices are currently "open" (gray), which are "closed" (black) and which are unexplored yet (white).

In addition, when you use "timestamping" of the colorings (which is a list saying when you color each vertex in the order it occurd) of DFS using 3 colors - you can find out interesting properties about the graph, like backedges. This is used for example to determine if a graph is acyclic or not.

Note that for the sole purpose of discovering a graph - the 3 colors are indeed not mandatory, and indeed exercise 22-3.4 asks you to show that.

Answer 2

You are correct.

Instead of coloring a vertex gray, you can color it black, and the algorithm still works.

It is easy to see that because nowhere in the code the colors gray and black are being checked. The only check is whether a vertex is white or not (the line marked as 2). This means all the colors which aren't white are equivalent.

I'm guessing the point of using a third color here is for verbosity and/or visualization purposes. If you were to display the graph while traversing it, the third color makes it much clearer what the status of the traversal process is, i.e. which nodes are currently "being visited".