algorithm - 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.