CLRS 22.3-1, How Come Solutions Online State There Can’t Be Edges From WHITE to GRAY nodes “at any point… during search”?


The exercise (from the book Introduction To Algorithms) states

Make a 3-by-3 chart with row and column labels WHITE, GRAY,and BLACK. In each cell (i, j) indicate whether, at any point during a depth-first search of a di- rected graph, there can be an edge from a vertex of color i to a vertex of color j . For each possible edge, indicate what edge types it can be. Make a second such chart for depth-first search of an undirected graph.

The colors WHITE, GRAY, BLACK correspond to Undiscovered, discovered but not finished, and finished. The following solution is what multiple sites & universities have posted(such as: walkccc, Rutgers University):

 |       | WHITE         | GRAY                | BLACK                | |-------|---------------|---------------------|----------------------| | WHITE | All kinds     | Cross, Back         | Cross                | | GRAY  | Tree, Forward | Tree, Forward, Back | Tree, Forward, Cross | | BLACK | -             | Back                | All kinds            | 

I will draw a minimal counter example as it helps understand my conflict:

counter-example

  • Start at node 0: 0 is GRAY
  • PAUSE
  • At this point, 3 is still white and has an edge to 0
  • Resume and keep going, eventually the edge from 3 to 0 will be discovered as a tree edge

This contradicts the solutions saying you can only have Cross/Back edges going form WHITE->GRAY. This example can be easily modified to contradict many of the elements in the table. I think the solutions are doing one of the following:

  • Assuming that the graph is a tree and that we start at its root. (Wrong as DFS doesn’t need a tree graph and any node can be started from).
  • More likely (Just thought of this), interpreting the question of "can there be an edge" as "can there be an edge that we have discovered". In which case, the solutions work, as although the edge from 3->0 was a WHITE->GRAY edge at one point, we hadn’t discovered it yet.