☕ DSA Java Articles

Topics › Graphs › Topo Sort and Problems

Detect a cycle in a directed graph

Hard TUF ID 500 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a directed graph with V vertices numbered 0 to V - 1 and a list of edges, where {u, v} is an edge from u to v. Return true if the graph contains at least one directed cycle, that is, a walk that follows edge directions and comes back to where it started. The graph may be disconnected and may contain self-loops ({u, u}) or repeated edges.

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           // 3 is reachable along two routes, but nothing leads back

Example 2 is the important one. In an undirected graph, meeting an already visited node that is not your parent means a cycle. Here a DFS from 0 visits 1, then 3, then backs out and visits 2, which points at 3 again. Node 3 is already visited, yet there is no cycle, because no edge leads from 3 back towards 0. Directed cycles need a different test, and this article shows three.

Approach 1: Brute force

Intuition. A directed cycle exists exactly when some node s can reach itself by following at least one edge. So ask that question for every node: start a search from the out-neighbours of s and see whether s ever shows up. The search is an ordinary graph traversal with a fresh seen array per start, which is why the cost multiplies.

Algorithm.

  1. Build the adjacency list.
  2. For every node s: push all of s’s out-neighbours on a stack and run an iterative DFS with a fresh seen array.
  3. If the popped node is s, we walked back to the start: return true.
  4. If no start finds itself, return false.
static List<List<Integer>> buildAdj(int V, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) adj.get(e[0]).add(e[1]);
    return adj;
}

static boolean bruteForce(int V, int[][] edges) {
    List<List<Integer>> adj = buildAdj(V, edges);
    for (int s = 0; s < V; s++) {
        boolean[] seen = new boolean[V];
        Deque<Integer> stack = new ArrayDeque<>(adj.get(s));
        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (u == s) return true;                      // walked back to the start
            if (seen[u]) continue;
            seen[u] = true;
            for (int v : adj.get(u)) stack.push(v);
        }
    }
    return false;
}

A self-loop {u, u} is handled naturally: u is its own out-neighbour, so it is on the stack from the very start and is popped immediately.

Complexity. Time O(V × (V + E)): up to V separate traversals, each touching every node and edge once. Space O(V + E) for the adjacency list, the seen array and the stack. For V = E = 10^5 that is about 2 × 10^10 steps, so we need a single traversal that answers the question for the whole graph.

Approach 2: DFS with path marking

Intuition. During a recursive DFS, the chain of calls currently on the stack is a path from the root to the node being explored. If we are at u and see an edge u → v where v is on that path, then v ⇝ u → v is a cycle. If v was visited earlier but has already returned (it is no longer on the path), the edge only means “we have been there”, which is exactly the diamond in Example 2.

So we keep two marks:

Why does this catch every cycle? Take any cycle and let c be its first node that the DFS visits. At that moment every other node of the cycle is unvisited and reachable from c, so the DFS will reach all of them before c returns. In particular it reaches the node x with the edge x → c while c is still on the path, and the check onPath[c] fires.

Algorithm.

  1. For every unvisited node, start dfs.
  2. In dfs(u): mark visited[u] and onPath[u].
  3. For each neighbour v: if onPath[v], return true. If v is unvisited and dfs(v) finds a cycle, return true.
  4. Before returning false, clear onPath[u].
static boolean dfsPathVisited(int V, int[][] edges) {
    List<List<Integer>> adj = buildAdj(V, edges);
    boolean[] visited = new boolean[V], onPath = new boolean[V];
    for (int i = 0; i < V; i++) {
        if (!visited[i] && dfs(i, adj, visited, onPath)) return true;
    }
    return false;
}

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

On Example 2 the trace is: enter 0, enter 1, enter 3 (no edges), leave 3, leave 1, enter 2, look at 3: visited[3] is true but onPath[3] is false, so no cycle. Without the onPath distinction this graph would be misreported.

Complexity. Time O(V + E): each node is entered once and each edge is examined once. Space O(V) for the two arrays plus a recursion depth of up to V. That depth is the practical weakness: a path of 10^5 nodes can overflow Java’s default thread stack.

Approach 3: Optimal, Kahn’s algorithm

Intuition. This problem sits in the topological sort section for a reason. A topological order (every edge points from an earlier node to a later one) exists if and only if the graph has no cycle. Kahn’s algorithm builds such an order by repeatedly removing a node with in-degree 0, a node nothing depends on any more, and lowering the in-degree of its neighbours.

Now look at a node on a cycle. Its predecessor on the cycle also lies on the cycle, so that incoming edge can only disappear once the predecessor is removed, which needs its predecessor removed first, and so on all the way around. No node of the cycle ever reaches in-degree 0. Nodes that can only be reached through the cycle are stuck as well. Conversely, a graph without a cycle always has some node with in-degree 0 (walk backwards along incoming edges; without a cycle you must stop somewhere), so Kahn’s algorithm removes everything.

The test is therefore one comparison: cycle exists ⇔ fewer than V nodes were removed.

Algorithm.

  1. Compute the in-degree of every node.
  2. Put every node with in-degree 0 in a queue.
  3. Pop a node, count it as removed, and decrement the in-degree of each out-neighbour; push any neighbour that drops to 0.
  4. Return removed < V.
static boolean kahn(int V, int[][] edges) {
    List<List<Integer>> adj = buildAdj(V, edges);
    int[] indegree = new int[V];
    for (int[] e : edges) indegree[e[1]]++;
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < V; i++) if (indegree[i] == 0) queue.add(i);
    int removed = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        removed++;
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) queue.add(v);
        }
    }
    return removed < V;                                   // nodes never freed sit on or behind a cycle
}

Dry run on V = 5, edges 0→1, 1→2, 2→3, 3→1, 3→4 (cycle 1 → 2 → 3 → 1, with 4 hanging behind it):

step queue removed in-degrees (0..4)
start [0] 0 0, 2, 1, 1, 1
pop 0 [] 1 0, 1, 1, 1, 1
queue empty   1 node 1 still waits for edge 3→1

Only one of five nodes was removed, so the answer is true. Node 4 is not on the cycle but is also never freed, which is why the comment in the code says “on or behind a cycle”.

Complexity. Time O(V + E): every node enters the queue at most once and every edge is decremented once. Space O(V) for the in-degree array and the queue (plus O(V + E) for the adjacency list, which all approaches share).

Both Approach 2 and Approach 3 are linear. Kahn’s algorithm is iterative, so it cannot overflow the stack, and the same code also produces a topological order when there is no cycle. The DFS version is the better tool when you need to print the cycle, because the nodes on onPath at the moment of detection are exactly the cycle plus the path leading to it.

Edge cases and pitfalls