Detect a Cycle in a Directed Graph

Given a directed graph, return true if it contains a cycle: a path that starts and ends at the same vertex by following edges in their direction.

Example 1: has a cycle

graph LR
    0 --> 1
    1 --> 2
    2 --> 3
    3 --> 1

Text

Output: true   (1 -> 2 -> 3 -> 1)

Example 2: no cycle

graph LR
    0 --> 1
    0 --> 2
    1 --> 2

Text

Output: false

Vertex 2 is reached by two different paths (0 → 2 and 0 → 1 → 2), but you can't get from 2 back to 0 or 1, so there's no cycle. A correct solution must not confuse "reached twice" with "a cycle".

Brute force: can a vertex reach itself?

A vertex v is on a cycle if one of its neighbors can reach v. For every vertex, start a traversal from each neighbor and check whether it gets back to v.

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

public class Main {
    static boolean reaches(List<List<Integer>> adj, int from, int target) {
        boolean[] visited = new boolean[adj.size()];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(from);
        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (v == target) {
                return true;
            }
            if (!visited[v]) {
                visited[v] = true;
                for (int w : adj.get(v)) {
                    stack.push(w);
                }
            }
        }
        return false;
    }

    static boolean hasCycle(List<List<Integer>> adj) {
        for (int v = 0; v < adj.size(); v++) {
            for (int w : adj.get(v)) {
                if (reaches(adj, w, v)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        List<List<Integer>> cyclic = List.of(List.of(1), List.of(2), List.of(3), List.of(1));
        List<List<Integer>> acyclic = List.of(List.of(1, 2), List.of(2), List.of());
        System.out.println(hasCycle(cyclic) + " " + hasCycle(acyclic));
    }
}

Output

true false

Time: O(V · (V + E)): up to one full traversal per vertex. Space: O(V).

A vertex can be pushed several times, but the visited check expands it only once. The target check comes before that check, so a vertex that was already expanded can still match.

Optimal: one DFS with three vertex states

A single visited flag isn't enough in a directed graph. In example 2, a DFS from 0 visits 0 → 1 → 2, then returns to 0 and sees the edge 0 → 2. Vertex 2 is already visited, but that's not a cycle, because 2 is finished. It isn't on the path we're currently exploring.

A cycle exists exactly when DFS finds an edge back to a vertex on the current path. So each vertex needs three states, stored in a Java enum (a type with a fixed set of named values):

State	Meaning
`NEW`	not visited yet
`ACTIVE`	on the current DFS path: we've started it but not finished it
`DONE`	fully explored, and no cycle goes through it

When exploring the edge v → w:

w is ACTIVE: the edge goes back to the current path, so there's a cycle.
w is NEW: explore it.
w is DONE: skip it. Everything reachable from w was already checked.

Walkthrough on example 1, starting at 0:

step	vertex	state change	edge checked	state of target
1	0	NEW → ACTIVE	0 → 1	NEW: explore
2	1	NEW → ACTIVE	1 → 2	NEW: explore
3	2	NEW → ACTIVE	2 → 3	NEW: explore
4	3	NEW → ACTIVE	3 → 1	ACTIVE: cycle

Java

import java.util.Arrays;
import java.util.List;

public class Main {
    enum State { NEW, ACTIVE, DONE }

    static boolean dfs(List<List<Integer>> adj, int v, State[] state) {
        state[v] = State.ACTIVE;
        for (int w : adj.get(v)) {
            boolean found = switch (state[w]) {
                case ACTIVE -> true;
                case NEW -> dfs(adj, w, state);
                case DONE -> false;
            };
            if (found) {
                return true;
            }
        }
        state[v] = State.DONE;
        return false;
    }

    static boolean hasCycle(List<List<Integer>> adj) {
        State[] state = new State[adj.size()];
        Arrays.fill(state, State.NEW);
        for (int v = 0; v < adj.size(); v++) {
            if (state[v] == State.NEW && dfs(adj, v, state)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        List<List<Integer>> cyclic = List.of(List.of(1), List.of(2), List.of(3), List.of(1));
        List<List<Integer>> acyclic = List.of(List.of(1, 2), List.of(2), List.of());
        List<List<Integer>> selfLoop = List.of(List.of(0));
        System.out.println(hasCycle(cyclic) + " " + hasCycle(acyclic) + " " + hasCycle(selfLoop));
    }
}

Output

true false true

Time: O(V + E): every vertex becomes ACTIVE once and DONE once, and every edge is checked once. Space: O(V) for the states and the recursion.

Alternative: Kahn's algorithm (topological sort)

A directed graph has no cycle exactly when its vertices can be put in a topological order, where every edge points forward. Kahn's algorithm builds that order:

Count each vertex's in-degree (the number of edges into it).
Put every vertex with in-degree 0 into a queue.
Repeatedly remove a vertex from the queue and output it. "Delete" its outgoing edges by lowering each neighbor's in-degree, and queue any neighbor that reaches 0.

If some vertices are never output, they're stuck behind a cycle (their in-degree never reaches 0).

Java

import java.util.ArrayDeque;
import java.util.List;
import java.util.Queue;

public class Main {
    static boolean hasCycle(List<List<Integer>> adj) {
        int n = adj.size();
        int[] indegree = new int[n];
        for (List<Integer> edges : adj) {
            for (int w : edges) {
                indegree[w]++;
            }
        }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int v = 0; v < n; v++) {
            if (indegree[v] == 0) queue.add(v);
        }
        int output = 0;
        while (!queue.isEmpty()) {
            int v = queue.poll();
            output++;
            for (int w : adj.get(v)) {
                indegree[w]--;
                if (indegree[w] == 0) {
                    queue.add(w);
                }
            }
        }
        return output < n;
    }

    public static void main(String[] args) {
        List<List<Integer>> cyclic = List.of(List.of(1), List.of(2), List.of(3), List.of(1));
        List<List<Integer>> acyclic = List.of(List.of(1, 2), List.of(2), List.of());
        System.out.println(hasCycle(cyclic) + " " + hasCycle(acyclic));
    }
}

Output

true false

Time: O(V + E). Space: O(V). No recursion, and the same loop gives you a topological order when there's no cycle. Course Schedule uses it to order courses by their prerequisites.

Edge cases

Self-loop (v → v): a cycle.
Disconnected graph: the outer loop starts a DFS from every unvisited vertex, so cycles in any part are found.
Undirected graphs need a different check, since every edge goes both ways. Use union-find, as in Graph Valid Tree.