Graph

whitegray (on stack)black

1 / 10

Speed

Color every vertex white (6 vertices). The search moves each node white → gray (on the stack) → black (finished).

Node colors

A:WB:WC:WD:WE:WF:W

Recursion stack

— empty —

cycle-detection.js

1const WHITE = 0, GRAY = 1, BLACK = 2;

3function hasCycle(u) {

4 color[u] = GRAY; // on the stack

5 for (const v of adj[u]) {

6 if (color[v] === GRAY)

7 return true; // back edge!

8 if (color[v] === WHITE

9 && hasCycle(v)) return true;

10 }

11 color[u] = BLACK; // done

12 return false;

13}

Click a node to choose where the search starts · Toggle DAG / cyclic to compare outcomes

About the Cycle Detection (Directed) algorithm

Detect cycles in a directed graph with three-color DFS: white unvisited, gray on the recursion stack, black fully explored. A back edge to a gray node means cycle.

Category: Graph
Difficulty: Medium
Time complexity: O(V+E)
Space complexity: O(V)