Introduction

Regular depth-first search already works on directed graphs, but it must track state carefully when cycles are present. Without that extra bookkeeping, recursion can loop forever or report misleading traversal results.

What DFS Must Track in a Cyclic Directed Graph

For an acyclic tree, a simple visited set is enough. For a cyclic directed graph, that is only part of the story. You often need three states:

• unvisited
• currently in the active recursion stack
• fully processed

These are commonly called:

• white
• gray
• black

Why does this matter? Because seeing an already visited node is not always the same thing as seeing a cycle edge. A node currently in the active stack means a back edge and therefore a cycle. A node that is fully processed does not.

Modified DFS with Colors

Here is a clean Python implementation.

1def dfs_traverse(graph):
2    color = {node: "white" for node in graph}
3    order = []
4    cycles = []
5    parent = {}
6
7    def build_cycle(start, end):
8        path = [start]
9        current = start
10        while current != end:
11            current = parent[current]
12            path.append(current)
13        path.reverse()
14        path.append(end)
15        return path
16
17    def visit(node):
18        color[node] = "gray"
19
20        for neighbor in graph[node]:
21            if color[neighbor] == "white":
22                parent[neighbor] = node
23                visit(neighbor)
24            elif color[neighbor] == "gray":
25                cycles.append(build_cycle(node, neighbor))
26
27        color[node] = "black"
28        order.append(node)
29
30    for node in graph:
31        if color[node] == "white":
32            visit(node)
33
34    return order, cycles
35
36
37graph = {
38    "A": ["B"],
39    "B": ["C", "D"],
40    "C": ["A"],
41    "D": ["E"],
42    "E": [],
43}
44
45order, cycles = dfs_traverse(graph)
46print(order)
47print(cycles)

This does three useful things:

• traverses all reachable nodes
• avoids infinite recursion on cycles
• records cycle information when a back edge is found

Why Gray Nodes Matter

Suppose the traversal goes from A to B to C, and then C points back to A.

At that moment:

• 'A is gray'
• 'B is gray'
• 'C is gray'

Seeing an edge from C to A tells you the search found a path back into the current recursion chain. That is a cycle. If A were black instead, it would mean A had already been completely explored earlier, which is different.

This is the essential DFS modification for cyclic directed graphs.

If You Only Need Safe Traversal

If cycle reconstruction is unnecessary and you only want to visit each node once safely, the algorithm can be simpler.

1def traverse_once(graph, start):
2    visited = set()
3    result = []
4
5    def visit(node):
6        if node in visited:
7            return
8        visited.add(node)
9        result.append(node)
10        for neighbor in graph.get(node, []):
11            visit(neighbor)
12
13    visit(start)
14    return result
15
16
17graph = {
18    1: [2],
19    2: [3],
20    3: [1, 4],
21    4: []
22}
23
24print(traverse_once(graph, 1))

This avoids infinite loops, but it loses the extra meaning of active-stack detection. So use this version only when safe traversal is enough and cycle classification is not required.

Recursive vs Iterative DFS

Recursive DFS is concise, but very deep graphs can hit recursion limits in Python or stack limits in other languages. An iterative version with an explicit stack is better when graph depth is unpredictable.

The same state concept still applies:

• maintain a visited or color map
• distinguish active exploration from finished processing when cycle detection matters

So the modification is conceptual, not tied to recursion specifically.

Common Uses

This pattern appears in:

• cycle detection in dependency graphs
• deadlock analysis
• graph validation before topological sorting
• compiler and build-system dependency checks

In all of those cases, "visited" is not enough. You need to know whether the node is being explored right now.

Common Pitfalls

Using only a visited set and assuming every repeated node implies a cycle gives false positives in directed graphs.

Forgetting to mark a node as fully processed after exploring its outgoing edges leaves the search state inconsistent.

Trying to reconstruct a cycle without a parent map makes the reporting logic much harder than it needs to be.

Using plain recursive DFS on a very deep graph can fail because of recursion depth even when the algorithm is logically correct.

Summary

• DFS on cyclic directed graphs needs more state than a simple visited set.
• The standard modification is a three-color or active-stack approach.
• A gray-to-gray edge during recursion indicates a cycle.
• Use a parent map if you want to reconstruct the actual cycle path.
• If you only need safe traversal, a visited set is enough, but it does less than full cycle-aware DFS.