A settlement batch is a graph of jobs: capture before ledger, ledger before notify. Someone adds notify → capture so a failed ping retries the chain. The worker DFS-walks “must finish before” edges and never returns. StackOverflowError at 2 a.m. The code had a visited set. Visited is not the bug.
A directed cycle is an edge to a gray vertex still on the DFS stack. An undirected cycle is an edge to a seen neighbor that is not the parent. Same walk as DFS. Different test on the neighbor you just saw.
This post is those two tests. Families and the catalog live on the Algorithms Roadmap. The layout is an adjacency list in Graphs. Topological sort already proves a DAG when Kahn emits n vertices — if it emits fewer, there is a directed cycle and you can stop. Here you stay on the graph and name the back edge.
Visited is not a cycle
A diamond is not a loop. Two paths into the same finished job are how DAGs look in production.
0 → 1 → 3
0 → 2 → 3DFS from 0 finishes 3 via 1, then reaches 3 again from 2. If “already seen” means cycle, you reject a legal order. The second edge into 3 is a merge, not a return to a job that is still running. A boolean visited on a directed graph cannot tell those apart. You need the color of this path.
Note: Restart from every white vertex. A cycle in a second component is still a cycle. Starting only at 0 is how a test graph stays green.
Directed: white, gray, black
| Color | Meaning |
|---|---|
| White | Unseen |
| Gray | On the current DFS path (recursion stack) |
| Black | Finished — all descendants walked |
- Paint the vertex gray when you enter it.
- For each neighbor: gray is a back edge — a cycle. White means recurse. Black means a finished subtree; ignore it.
- Paint the vertex black when every neighbor is done.
Gray is the recursion stack. An edge into gray is an edge into an ancestor that has not finished. An edge into black is the diamond: the other path already returned. A self-loop is a neighbor equal to self while gray — cycle, immediately. You do not need finish clocks; DFS owns those. Stack membership is the test.
A walked 3-color DFS
Edges 0→1, 1→2, 2→1, 0→3. Cycle is 1 → 2 → 1. Then the same walk on the diamond.
cycle: 0 → 1 ⇄ 2 diamond: 0 → 1 → 3
↓ ↓ ↑
3 2 ──────┘
dfs(0) 0 GRAY
dfs(1) 1 GRAY
dfs(2) 2 GRAY
neighbor 1: GRAY → cycle (back edge 2→1)
stop. gray on stack: {0, 1, 2}
dfs(0) 0 GRAY
dfs(1) 1 GRAY
dfs(3) 3 GRAY → BLACK
1 BLACK
dfs(2) 2 GRAY
neighbor 3: BLACK → not a cycle
2 BLACK
0 BLACKBlack is the signal that 3 is done. Treating it as gray is the bug you shipped at 2 a.m.
Undirected: skip the parent
An undirected edge is stored twice. After you walk 0—1, 1 lists 0. That is the edge you just used, not a cycle. Skip the parent. Any other seen neighbor is a cycle. A boolean seen is enough once that skip is in the loop.
no cycle: 0 — 1 — 2 cycle: 0 — 1
| \ /
3 2
dfs(0, -1) → 1 (parent 0) → 2 (parent 1) → 3 (parent 1)
each back-to-parent skipped; nobody else is seen
dfs(0, -1) → 1 (parent 0) → 2 (parent 1)
2 sees 0: seen, 0 ≠ parent 1 → cycleA self-loop (v == u) is not the parent. Cycle. A parallel copy of 0—1 in 0’s list is the same: the extra copy is not the parent.
Note: If you stored the undirected graph with only one direction per pair, the parent trick is lying. Fix the layout first (Graphs).
Java sketch
Directed: index color[u] by vertex id. The outer loop covers every component.
static final int WHITE = 0, GRAY = 1, BLACK = 2;
static boolean hasDirectedCycle(List<List<Integer>> adj) {
int n = adj.size();
int[] color = new int[n];
for (int u = 0; u < n; u++) {
if (color[u] == WHITE && dfsDirected(u, adj, color)) {
return true;
}
}
return false;
}
static boolean dfsDirected(int u, List<List<Integer>> adj, int[] color) {
color[u] = GRAY;
for (int v : adj.get(u)) {
if (color[v] == GRAY) {
return true;
}
if (color[v] == WHITE && dfsDirected(v, adj, color)) {
return true;
}
}
color[u] = BLACK;
return false;
}When color[v] == GRAY, the cycle is the gray path from v to u plus u → v. Record parent[u] if the caller wants the vertices, not only a boolean.
Undirected: seen plus the parent. The parent is the only safe seen neighbor.
static boolean hasUndirectedCycle(List<List<Integer>> adj) {
int n = adj.size();
boolean[] seen = new boolean[n];
for (int u = 0; u < n; u++) {
if (!seen[u] && dfsUndirected(u, -1, adj, seen)) {
return true;
}
}
return false;
}
static boolean dfsUndirected(int u, int parent, List<List<Integer>> adj,
boolean[] seen) {
seen[u] = true;
for (int v : adj.get(u)) {
if (v == parent) {
continue;
}
if (seen[v]) {
return true;
}
if (dfsUndirected(v, u, adj, seen)) {
return true;
}
}
return false;
}Vertex ids are 0 … n-1. String job names get a side index. Do not dump the gray path into a HashSet of strings on every call if you already have an int[].
Note: The sketches omit reconstructing the cycle and omit an explicit stack. DFS owns recursion versus a stack. If you walk with a stack, gray still means “pushed and not yet popped.”
Complexity
Let n be |V|, m be |E|. One DFS walks each vertex once and each adjacency-list entry once.
| Time | O(n + m) |
| Extra memory | O(n) colors or seen, plus O(n) recursion depth on a worst path |
| Directed test | Neighbor is gray |
| Undirected test | Neighbor is seen and not the parent |
A matrix still costs O(n²) to scan neighbors because that is the layout. On a sparse list the procedure is linear in the edges you stored. Glossary for the O-notation lives on the Algorithms Roadmap.
When not to hand-roll this
Skip a custom color walk when:
- You already ran Kahn. n vertices emitted means a DAG; fewer means a directed cycle. This post is for the back edge itself, or for undirected edges.
- The structure is a singly linked list. Slow/fast on
nextis the list loop (Two Pointers), not a coloring argument. - The graph is a tree by construction. Walking an org chart “to be safe” is not a detector.
- You needed an order to run the work. A boolean cycle does not emit a schedule. Topological sort does.
Do not treat every second visit as a cycle on a directed graph. That is how a diamond becomes an incident. Also skip it when the product question is not “does this loop” — reachability and “what runs first” share the list, not this test.
JDK: colors, not a CycleDetector
There is no java.util.CycleDetector. The pieces are the list you already built and an int[].
- Layout:
List<List<Integer>>orMap<K, List<K>>from the graphs post - Directed:
int[] colorwith three states - Undirected:
boolean[] seenand a parent argument
Prefer Kahn’s count of emitted vertices when the graph is directed and you already needed a build order. Reach for the sketch when you must name the back edge, or when the edges are undirected.
Do not wrap the gray path in a HashSet per call if ids are dense. Do not BFS with one visited set and call that directed cycle detection. Do not recurse on a 50,000-deep job chain without a depth budget or an explicit stack; the algorithm still holds, the JVM stack may not.
Cheat sheet
Job: decide whether a graph contains a cycle
Directed: 3-color DFS; gray = on stack; edge to gray = cycle
edge to black = diamond, not a cycle
Undirected: DFS; skip parent; any other seen neighbor = cycle
Components: restart from every white / unseen vertex
Time: O(n + m) on an adjacency list
Cousin: Kahn emitting n already proves a directed DAG
List cousin: slow/fast on next (not this coloring argument)
JDK: int[] color / boolean[] seen; no CycleDetector
Do not: boolean visited as a directed cycle testDo:
- Paint gray on enter, black on leave, for directed graphs.
- Skip the parent on undirected lists (both directions stored).
- Loop every component. Use Kahn’s n-count when you already came for a schedule.
Don’t:
- Treat a black (finished) vertex as a cycle on a DAG diamond.
- Forget that
u—vappears fromvas well. - Start DFS only at vertex 0 and declare the graph acyclic.
- Hand a directed color walk an undirected list without the parent skip, or the reverse.
Wrap-up
Cycle detection is a DFS neighbor test, not a second visited flag. Directed: only gray is a loop. Undirected: the neighbor you came from is legal; any other seen neighbor is not. Diamonds are why the boolean is wrong. Kahn already answered “is it a DAG?” when it emitted n; this post is the back edge and the parent skip. The JDK gives you arrays and lists, not a detector class. Hand-roll the colors when the graph and the question are yours. Otherwise take the schedule you already computed.