Topics › Graphs › Topo Sort and Problems

Detect A cycle in a Directed Graph using DFS

Hard TUF ID 2816 SDE

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a directed graph with V vertices numbered 0 to V - 1. adj.get(u) lists every vertex v such that there is an edge from u to v. Return true if the graph has a directed cycle: a walk that follows the arrows and returns to the vertex it started from. The graph may be disconnected, and it may contain self-loops (u -> u) or repeated edges. Use depth-first search.

Constraints: 1 ≤ V ≤ 10^5, 0 ≤ E ≤ 10^5.

Example 1

V = 4, edges: 0->1, 1->2, 2->0, 2->3
answer = true        // 0 -> 1 -> 2 -> 0

Example 2

V = 4, edges: 0->1, 0->2, 1->3, 2->3
answer = false       // a "diamond": 3 is reachable twice, but no arrow leads back up

Example 2 is the important one. Running an undirected-style check (“a visited neighbour that is not my parent means a cycle”) on it gives the wrong answer: DFS reaches 3 through 1, and later 2 finds 3 already visited. In a directed graph that only means two routes lead into 3, not that you can come back out of 3 to where you started.

Approach 1: Brute force, can each vertex get back to itself?

Intuition. A vertex s lies on a directed cycle exactly when some walk leaves s and returns to s. So start a search at every vertex in turn and ask whether any edge reachable from it points back into s. If one does for any s, there is a cycle.

Algorithm.

1. For each vertex s, create a fresh seen array.
2. DFS from s. Whenever an edge x -> y has y == s, return true.
3. Otherwise continue into unseen vertices.
4. If no start vertex succeeds, return false.

static boolean bruteForce(int V, List<List<Integer>> adj) {
    for (int s = 0; s < V; s++) {
        boolean[] seen = new boolean[V];
        if (returnsTo(adj, s, s, seen)) return true;
    }
    return false;
}

/** DFS from x: is there an edge into target from anything reachable? */
static boolean returnsTo(List<List<Integer>> adj, int x, int target, boolean[] seen) {
    seen[x] = true;
    for (int y : adj.get(x)) {
        if (y == target) return true;
        if (!seen[y] && returnsTo(adj, y, target, seen)) return true;
    }
    return false;
}

Complexity. Time O(V · (V + E)): up to a full DFS from each of the V vertices. Space O(V) for seen and the recursion.

The repeated work is huge: a long chain is re-explored from each of its vertices. We want one DFS that both explores and detects.

Approach 2: Optimal, DFS with a “currently on the path” marker

Intuition. During a DFS, the recursion stack is a path s -> ... -> x that we are currently standing on. When we look at an edge x -> y, there are three possibilities:

• y was never visited: explore it.
• y is visited and still on the current path: then y -> ... -> x already exists along the path, and the edge x -> y closes it. That is a cycle.
• y is visited but already finished (the DFS returned from it): everything reachable from y has been fully explored. If y could reach back to x, that would have been discovered while y was being explored, so this edge cannot create a cycle. This is the diamond case.

So we keep two boolean arrays. visited[x] is set once and never cleared, which keeps the total work linear. onPath[x] is set when the DFS enters x and cleared when it leaves.

Why does this catch every cycle? Take any cycle and let w be the first of its vertices that the DFS enters. At that moment all the other cycle vertices are unvisited and reachable from w along the cycle, so the DFS will enter all of them before it leaves w. In particular it enters the vertex p whose edge on the cycle is p -> w, and when it examines that edge, w is still on the path. The check fires.

Algorithm.

1. For each unvisited vertex s, run dfs(s).
2. dfs(x): set visited[x] and onPath[x]. For each edge x -> y:
   • if onPath[y], return true;
   • if y is unvisited and dfs(y) returns true, return true.
3. Clear onPath[x] and return false.

static boolean optimal(int V, List<List<Integer>> adj) {
    boolean[] visited = new boolean[V];
    boolean[] onPath = new boolean[V];
    for (int s = 0; s < V; s++) {
        if (!visited[s] && dfs(adj, s, visited, onPath)) return true;
    }
    return false;
}

static boolean dfs(List<List<Integer>> adj, int x, boolean[] visited, boolean[] onPath) {
    visited[x] = true;
    onPath[x] = true;
    for (int y : adj.get(x)) {
        if (onPath[y]) return true;                   // back edge: y is an ancestor of x
        if (!visited[y] && dfs(adj, y, visited, onPath)) return true;
    }
    onPath[x] = false;                                // leaving x: it is no longer on the current path
    return false;
}

Dry run on example 2 (the diamond), where plain “visited” would fail:

On example 1 the path becomes 0, 1, 2, and the edge 2 -> 0 finds 0 on the path, returning true.

Complexity. Time O(V + E): each vertex is entered once and each edge examined once. Space O(V) for the two arrays and recursion depth.

Approach 3: Optimal, three colours with an explicit stack

Intuition. The two booleans describe three states, often called colours: white (never visited), grey (on the current path), and black (finished). A single int[] state holds them. To avoid deep recursion on long chains, we simulate the call stack. Each vertex on the stack remembers the index of the next out-edge to examine in next[x], exactly like the loop variable of the recursive call. When a vertex has no edges left, it turns black and is popped.

Algorithm.

1. For each white vertex s: colour it grey and push it.
2. While the stack is not empty, look at the top x.
   • If all its edges are done, colour it black and pop.
   • Otherwise take the next edge x -> y. Grey y means a cycle: return true. White y: colour it grey and push it. Black y: ignore.
3. Return false.

static boolean optimalIterative(int V, List<List<Integer>> adj) {
    int[] state = new int[V];
    int[] next = new int[V];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int s = 0; s < V; s++) {
        if (state[s] != 0) continue;
        state[s] = 1;
        stack.push(s);
        while (!stack.isEmpty()) {
            int x = stack.peek();
            if (next[x] == adj.get(x).size()) {
                state[x] = 2;                         // all edges out of x explored
                stack.pop();
                continue;
            }
            int y = adj.get(x).get(next[x]++);
            if (state[y] == 1) return true;
            if (state[y] == 0) {
                state[y] = 1;
                stack.push(y);
            }
        }
    }
    return false;
}

Complexity. Time O(V + E). Space O(V), all on the heap, so a chain of 10^5 vertices is no problem.

Edge cases and pitfalls

• Do not use the undirected parent trick. In a directed graph, 0 -> 1 and 1 -> 0 form a genuine cycle of length two, yet 0 is 1’s parent. The parent check would ignore it.
• Do not use “visited” alone. The diamond shows that reaching a visited vertex is normal in a DAG. Only a vertex that is still on the path proves a cycle.
• Remember to clear onPath on the way out. Forgetting this turns every finished vertex into a false alarm.
• Never clear visited. Re-exploring finished vertices from each new root is correct but brings back the quadratic cost of Approach 1.
• Self-loops. An edge x -> x finds x on its own path, so it is reported, which is right.
• Repeated edges. 0 -> 1 listed twice is harmless: when the second copy is examined, 1 is already finished and the edge is ignored.
• Disconnected graphs. Start from every unvisited vertex; a cycle may hide in a component that vertex 0 cannot reach.

Related problems

• Detect A cycle in a Directed Graph using BFS solves the same task with Kahn’s algorithm.
• Topological Sort DFS uses the same DFS; a topological order exists exactly when this method returns false.
• Detect A cycle in Undirected Graph using DFS is the undirected version, where a parent check is enough.
• Course Schedule I is this problem in disguise: the courses can be finished if and only if the prerequisite graph has no cycle.
• Find eventual safe states reuses the grey and black colours to find vertices that cannot reach a cycle.