Card 07/ 10
Detecting a Cycle in a Directed Graph With Three Colours
Meeting a grey vertex means a path that returns to itself; meeting a black one means nothing.
A directed graph has a cycle exactly when depth-first search finds an edge to a grey vertex, one that is on the current path and not yet finished. This card shows why that test is right, why a plain visited set gets it wrong, and runs both on one graph without a cycle and the same graph with one edge added.
In a directed graph each edge goes one way, written A->B. A cycle is a path that follows the edges and comes back to where it started. Depth-first search colours a vertex grey when it enters and black when it finishes, so the grey vertices at any moment are exactly the path from the start to the current vertex. An edge from the current vertex to a grey one closes that path into a loop. An edge to a black vertex reaches somewhere already fully explored, and since nothing reachable from a black vertex leads back to the current path, no cycle runs through it.
The first graph has edges A->B, A->C, B->D, C->B and D->E. It has no cycle, but B can be reached two ways, from A and from C. The second graph adds E->C, which closes the loop C->B->D->E->C. The table gives each test's verdict on each graph, from a run that visits neighbours in alphabetical order.
| Graph | Visited set | Three colours | Right answer |
|---|---|---|---|
| Without E->C | C->B reaches a visited vertex: cycle | C->B reaches a black vertex and is ignored: no cycle | No cycle |
| With E->C | C->B and A->C reach visited vertices: cycle | C->B reaches grey B, closing B D E C: cycle | Cycle |
On the first graph the search goes A, B, D, E, and every one of those finishes before it backs up to A and tries C. When C looks at B, B is black. A visited set only knows that B was seen, so it reports a cycle where two paths merge. Three colours know that B is finished and so not on the current path, and give the right answer.
On the second graph the search goes A, B, D, E and then follows E->C while B, D and E are all still grey. C's edge to B reaches a grey vertex, and the grey vertices from B to C are the cycle: B, D, E, C and back to B. The visited set says cycle here too, but for both edges, including A->C, which is on no cycle at all; it is right by accident.
In an undirected graph the test is different, because every edge can be walked back the way it came. There a cycle is an edge to any visited vertex other than the parent the search arrived from, and two colours are enough.
← → move through sections and cards