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
- depth-first search — A graph search that follows one path as deep as it can go, then backs up to the last choice point and tries the next branch.
- cycle — A path in a graph that starts and ends at the same vertex.
- directed acyclic graph — A directed graph with no cycles, so following edges can never bring you back to where you started.
Taught in
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers