Definition
- Three-colour DFS – each node starts white (unvisited), becomes grey when entered (on the recursion stack), and becomes black when fully explored.
- Back edge detection – reaching a grey neighbour during DFS means that neighbour is an ancestor on the current path, so the edge back to it closes a cycle.
- Black neighbour is safe – a black neighbour was fully explored on an earlier path and produced no cycle, so it can be skipped.
- Topological sort variant – this is the DFS counterpart to Kahn's in-degree BFS method for detecting cycles in a directed graph.
- Linear time – O(V + E) because each node and edge is processed exactly once.
At the National Bank of India, a set of dependent approval steps must not contain a circular dependency. If step A waits on step B which waits back on step A, the workflow deadlocks. The three-colour DFS checks whether any such loop exists by tracking which steps are currently being explored (grey) versus fully processed (black).
Understanding the Concepts
What is the Course Schedule Cycle Check problem?
The problem gives a number of courses and a list of prerequisite pairs [a, b] meaning course a requires course b first. The task is to determine whether all courses can be completed, which is possible only if the dependency graph has no cycle. If a cycle exists, no valid ordering exists.
package com.bank.service;
import java.util.*;
public class CourseScheduleCycleCheck {
private static final int WHITE = 0, GREY = 1, BLACK = 2;
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);
int[] colour = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
if (colour[i] == WHITE && hasCycle(i, adj, colour)) return false;
}
return true;
}
private boolean hasCycle(int node, List<List<Integer>> adj, int[] colour) {
colour[node] = GREY;
for (int next : adj.get(node)) {
if (colour[next] == GREY) return true; // back edge: cycle
if (colour[next] == WHITE && hasCycle(next, adj, colour)) return true;
}
colour[node] = BLACK;
return false;
}
public static void main(String[] args) {
CourseScheduleCycleCheck solver = new CourseScheduleCycleCheck();
System.out.println("No cycle: " + solver.canFinish(2, new int[][]{{1, 0}}));
System.out.println("Cycle: " + solver.canFinish(2, new int[][]{{1, 0}, {0, 1}}));
}
}
No cycle: true
Cycle: false
Why use three colours instead of a simple visited set?
A simple visited set cannot distinguish between a node that is currently on the recursion stack (an ancestor) and a node that was fully explored on a different path. In a directed graph, reaching a fully explored node is not a cycle, it is a cross edge. Only reaching a node that is currently on the recursion stack (grey) is a back edge that indicates a cycle. The third colour (black) lets us skip fully explored nodes safely.
package com.bank.service;
public class WhyThreeColours {
// Two-colour approach (visited/not visited):
// - Cannot distinguish ancestor (back edge) from cross edge
// - Would falsely report a cycle on a diamond-shaped DAG
//
// Three-colour approach:
// WHITE = not visited
// GREY = on current recursion stack (ancestor)
// BLACK = fully explored, safe to skip
public static void main(String[] args) {
// Diamond DAG: 0->1, 0->2, 1->3, 2->3
// Two-colour: visiting 3 from 1, then from 2 looks like a cycle (WRONG)
// Three-colour: 3 is BLACK after path 1->3, so path 2->3 skips it (CORRECT)
System.out.println("Three colours distinguish back edges from cross edges.");
}
}
How does the DFS colouring algorithm work step by step?
When we enter a node, we colour it grey (on the stack). We then visit each neighbour. If a neighbour is grey, we found a back edge and report a cycle. If a neighbour is white, we recurse into it. If a neighbour is black, we skip it. After all neighbours are processed, we colour the node black (fully explored).
package com.bank.service;
import java.util.*;
public class DFSColouringTrace {
private static final int WHITE = 0, GREY = 1, BLACK = 2;
public static void main(String[] args) {
// Graph: 0->1, 1->2, 2->0 (cycle)
List<List<Integer>> adj = List.of(
List.of(1), List.of(2), List.of(0)
);
int[] colour = {WHITE, WHITE, WHITE};
System.out.println("Enter 0: colour=GREY");
colour[0] = GREY;
System.out.println(" Enter 1: colour=GREY");
colour[1] = GREY;
System.out.println(" Enter 2: colour=GREY");
colour[2] = GREY;
System.out.println(" Neighbour 0 is GREY => CYCLE DETECTED!");
}
}
Enter 0: colour=GREY
Enter 1: colour=GREY
Enter 2: colour=GREY
Neighbour 0 is GREY => CYCLE DETECTED!
How is this different from Kahn's in-degree BFS?
| Feature | DFS colouring | Kahn's BFS |
|---|---|---|
| Approach | recursive DFS with three colours | iterative BFS with in-degree counting |
| Cycle detection | grey neighbour = back edge | processed count < V = cycle |
| Output | boolean (cycle exists) | topological order + boolean |
| Stack usage | O(V) recursion depth | O(V) queue |
| Implementation | recursive, 3-state array | iterative, in-degree array + queue |
package com.bank.service;
import java.util.*;
public class KahnsAlgorithm {
public boolean canFinish(int n, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) {
adj.get(p[1]).add(p[0]);
inDegree[p[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) queue.add(i);
}
int processed = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
processed++;
for (int next : adj.get(node)) {
if (--inDegree[next] == 0) queue.add(next);
}
}
return processed == n; // if not, cycle exists
}
public static void main(String[] args) {
System.out.println("Kahn's: " + new KahnsAlgorithm().canFinish(3, new int[][]{{1,0},{2,1}}));
}
}
Kahn's: true
What are the edge cases?
Edge cases include no prerequisites (no edges, no cycle), a single course, self-loops (course requires itself), and disconnected components where a cycle exists in only one component.
package com.bank.service;
public class CycleEdgeCases {
public static void main(String[] args) {
CourseScheduleCycleCheck solver = new CourseScheduleCycleCheck();
// No prerequisites: always possible
System.out.println("No prereqs: " + solver.canFinish(3, new int[][]{}));
// Self-loop: course 0 requires course 0
System.out.println("Self-loop: " + solver.canFinish(1, new int[][]{{0, 0}}));
// Disconnected: cycle in one component
System.out.println("Disconnected cycle: " + solver.canFinish(4,
new int[][]{{1, 0}, {2, 3}, {3, 2}}));
}
}
No prereqs: true
Self-loop: false
Disconnected cycle: false
What are common mistakes?
The most common mistake is using only two colours (visited/unvisited) in a directed graph, which falsely reports cycles on diamond-shaped DAGs. Another mistake is not starting DFS from every unvisited node, which misses cycles in disconnected components.
Wrong code:
// WRONG: two colours only, false positive on diamond DAG
boolean[] visited = new boolean[n];
private boolean hasCycleBad(int node) {
if (visited[node]) return true; // BUG: black nodes also return true
visited[node] = true;
for (int next : adj.get(node)) {
if (hasCycleBad(next)) return true;
}
return false;
}
Correct code:
// CORRECT: three colours distinguish grey from black
private boolean hasCycleGood(int node, int[] colour) {
colour[node] = GREY;
for (int next : adj.get(node)) {
if (colour[next] == GREY) return true; // back edge
if (colour[next] == WHITE && hasCycleGood(next, colour)) return true;
}
colour[node] = BLACK;
return false;
}
When should you use this technique?
Use three-colour DFS for cycle detection in directed graphs where you need a boolean answer. If you also need the topological order, Kahn's BFS is more natural because it produces the order as a side effect. Both run in O(V + E) time.
package com.bank.service;
public class WhenToUseDFSColouring {
public static void main(String[] args) {
System.out.println("Use DFS colouring when:");
System.out.println(" - Need boolean cycle detection in directed graph.");
System.out.println(" - Natural recursive implementation.");
System.out.println("Use Kahn's BFS when:");
System.out.println(" - Need the topological order as output.");
System.out.println(" - Prefer iterative implementation.");
}
}
What should a senior engineer know?
A senior engineer knows that the grey colour is exactly the recursion stack membership, and that this is what distinguishes a back edge (cycle) from a cross edge (safe) or forward edge (safe) in a directed graph. They also know that in undirected graphs, you only need to check that you do not revisit the parent, because every edge back to a visited non-parent node is a cycle. In production at National Bank of India, the workflow engine validates that approval step dependencies form a DAG before saving the workflow, using three-colour DFS to catch circular dependencies immediately.
package com.bank.service;
public class SeniorCycleNotes {
// Edge classification in directed DFS:
// Tree edge: white -> grey (parent to child)
// Back edge: any -> grey (cycle!)
// Forward edge: any -> black (ancestor to descendant, safe)
// Cross edge: any -> black (between branches, safe)
public static void main(String[] args) {
System.out.println("Grey = on recursion stack => back edge => cycle.");
System.out.println("Black = fully explored => cross/forward edge => safe.");
System.out.println("Undirected: just check parent, no three colours needed.");
}
}
Visual Overview
DFS Three-Colour Cycle Detection
Graph: 0 -> 1 -> 2 -> 0 (cycle)
┌─────────────────────────────┐
│ Node 0: WHITE -> GREY │
│ ├─ Node 1: WHITE -> GREY │
│ │ ├─ Node 2: WHITE->GREY│
│ │ │ └─ Node 0: GREY! │ ◀── BACK EDGE = CYCLE
│ │ │ RETURN TRUE │
│ │ └─ RETURN TRUE │
│ └─ RETURN TRUE │
└─────────────────────────────┘
Diamond DAG (no cycle): 0->1, 0->2, 1->3, 2->3
┌───────────────────────────────┐
│ Node 0: WHITE -> GREY │
│ ├─ Node 1: WHITE -> GREY │
│ │ └─ Node 3: WHITE->GREY │
│ │ (no grey neighbours) │
│ │ Node 3: GREY -> BLACK│
│ │ Node 1: GREY -> BLACK │
│ ├─ Node 2: WHITE -> GREY │
│ │ └─ Node 3: BLACK (skip) │ ◀── SAFE, not a cycle
│ │ Node 2: GREY -> BLACK │
│ Node 0: GREY -> BLACK │
└───────────────────────────────┘
Result: no cycle (correct)
Key Takeaway
The Course Schedule Cycle Check uses three-colour DFS to detect cycles in a directed dependency graph. Each node starts white (unvisited), becomes grey when entered (on the recursion stack), and becomes black when fully explored. The cycle test is simple: if DFS reaches a grey neighbour, that neighbour is an ancestor on the current path, so the edge back to it closes a cycle.
The reason three colours are needed instead of a simple visited flag is that a simple flag cannot distinguish a back edge from a cross edge. In a diamond-shaped DAG, a two-colour approach falsely reports a cycle when the second path reaches a node already visited by the first path. The third colour (black) tells us that node was fully explored and is safe to skip.
Both three-colour DFS and Kahn's in-degree BFS run in O(V + E) time and detect cycles correctly. Kahn's is preferred when you also need the topological order as output, while DFS colouring is a natural recursive implementation for a boolean cycle check.
At the National Bank of India, the workflow engine validates that approval step dependencies form a DAG before saving a new workflow configuration. Three-colour DFS catches circular dependencies immediately, preventing deadlocks where step A waits on step B which waits back on step A. Explaining the white-grey-black states and that grey means recursion-stack membership is what shows an interviewer you understand the DFS variant of the Topological Sort pattern.
Remember one sentence: colour nodes white, grey (on stack), and black (done); reaching a grey neighbour means a back edge and therefore a cycle.
---