cycle detection

Finding whether a graph contains a cycle; in a directed graph, DFS with three colours finds one by spotting an edge back to a vertex still in progress.

In more detail

Vertices start white (unvisited), turn gray while their descendants are being explored, and turn black when finished. An edge to a gray vertex is a back edge: it points to an ancestor on the current path, so there is a cycle. Edges to black vertices are safe.

Related terms

Taught in

References