CLRS 22.3.1

Question

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

Answer 1

WHITE: Not Yet discovered i.e. Unexplored

GRAY: E-Node/Live Node i.e. being explored now

BLACK: Dead i.e. all its children and the node itself has been explored

There are 4 types of edges: Tree Edge, Forward Edge, Back Edge and Cross edge

Directed Graph

i / j	White	Gray	Black
White	Since we have no information about the discovery and finish time of i and j, therefore it can be any of the four edges.	Since discovery(i)>discovery(j), therefore ONLY back or cross edge possible. In other words, suppose if ij is a forward/tree edge, then i cannot be an unexplored node.	Since discovery(i)>discovery(j), & finish(i)>finish(j) therefore it is definitely a cross edge. In other words, since j is dead even before i got discovered. That implies that i and j cannot have an ancestor-descendant relationship, hence all other three edges ruled out.
Gray	Since discovery(i)<discovery(j), therefore it can be either Tree or Forward edge only.	Since both i and j are live at the same time, therefore the edge cannot be a cross edge. Can be any among Tree, Forward or Back.	We don’t know whether j died before/after i got discovered. But we know that finish(i)>finish(v). Hence it can be Forward, Tree or Cross edge.
Black	If there would have been an edge from i to j, then j wouldn’t be an unexplored node. NONE of the EDGE.	Since i is dead before j, therefore, i cannot be an ancestor of j. Therefore Forward/Tree edge ruled out. Since not ancestor, therefore discovery(i)>discovery(j) and hence Back/Cross edge.	Since we have no information about the discovery and finish time of i and j, therefore it can be any of the four edges.

You can notice that whenever we have a tree edge, there is also an entry for a Forward edge too. It is because it is just a matter of ordering which decides which will be a tree edge and a forward edge.