☕ DSA Java Articles

Topics › Graphs › Topo Sort and Problems

Detect A cycle in a Directed Graph using BFS

Hard TUF ID 2815 SDE

Java source ↗ Edit this article ↗

Problem

You are given a directed graph with V vertices numbered 0 to V - 1, where adj.get(u) lists every v with an edge u -> v. Return true if the graph contains a directed cycle, a walk along the arrows that returns to its start. The graph may be disconnected and may contain self-loops or repeated edges. Use a breadth-first technique.

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

Example 1

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

Example 2

V = 6, edges: 5->0, 4->0, 5->2, 4->1, 2->3, 3->1
answer = false       // a DAG: every arrow can be drawn pointing "downwards"

BFS has no recursion stack, so the DFS trick of checking “is this vertex on my current path?” is not available. The breadth-first answer comes from a different angle, in-degrees, and it is the same machinery that produces a topological order.

Approach 1: Brute force, BFS from every vertex

Intuition. Vertex s lies on a cycle if and only if there is a walk from s back to s. A BFS from s visits everything reachable from s; if any edge it scans points to s itself, the walk exists. Repeat for every vertex.

Algorithm.

  1. For each vertex s: start a BFS with a fresh seen array.
  2. For each dequeued x and each edge x -> y: if y == s, return true; otherwise enqueue y if unseen.
  3. After all start vertices, return false.
static boolean bruteForce(int V, List<List<Integer>> adj) {
    for (int s = 0; s < V; s++) {
        boolean[] seen = new boolean[V];
        Deque<Integer> queue = new ArrayDeque<>();
        seen[s] = true;
        queue.add(s);
        while (!queue.isEmpty()) {
            int x = queue.poll();
            for (int y : adj.get(x)) {
                if (y == s) return true;              // walked from s back to s
                if (!seen[y]) {
                    seen[y] = true;
                    queue.add(y);
                }
            }
        }
    }
    return false;
}

Complexity. Time O(V · (V + E)), one BFS per vertex. Space O(V) for one BFS at a time.

For V = E = 10^5 that is about 10^10 steps. The fix is to stop asking “does each vertex come back to itself?” and instead peel away the vertices that obviously cannot be on a cycle.

Approach 2: Optimal, Kahn’s algorithm

Intuition. Look at a vertex with in-degree 0, one that no arrow enters. It cannot be on a cycle, because a cycle enters each of its vertices. So we may delete it, together with its outgoing edges, without destroying any cycle. Deleting those edges lowers the in-degree of its successors, and some of them may now have in-degree 0 too. Keep peeling.

Two facts make this a complete test:

So: count how many vertices get removed. If it is V, the graph is acyclic; if fewer, a cycle exists. A queue holds the vertices whose in-degree has dropped to 0 and are waiting to be removed, which is why this is called the BFS method.

Algorithm.

  1. Compute indegree[v] for every vertex by scanning all edges.
  2. Enqueue every vertex with in-degree 0.
  3. While the queue is not empty: dequeue u, increment removed, and for each edge u -> v decrement indegree[v]; if it reaches 0, enqueue v.
  4. Return removed < V.
static boolean optimal(int V, List<List<Integer>> adj) {
    int[] indegree = new int[V];
    for (int u = 0; u < V; u++) {
        for (int v : adj.get(u)) indegree[v]++;
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int u = 0; u < V; u++) {
        if (indegree[u] == 0) queue.add(u);
    }
    int removed = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        removed++;
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) queue.add(v);     // v has no remaining prerequisites
        }
    }
    return removed < V;                               // vertices on or behind a cycle never reach in-degree 0
}

Dry run on example 1. Initial in-degrees: 0:0, 1:2, 2:1, 3:1, 4:1.

step dequeued in-degree changes queue after removed
start     [0] 0
1 0 1: 2 -> 1 [] 1

The queue is empty after one removal. Vertex 1 still has an arrow from 3, vertex 3 has one from 2, and vertex 2 has one from 1: the cycle keeps all three alive. removed = 1 < 5, so the answer is true. Notice that vertex 4 is not on the cycle but is also never removed, because it hangs behind the cycle. The leftover set is “cycle plus everything downstream of it”, not just the cycle itself.

On example 2, the in-degrees are 0:2, 1:2, 2:1, 3:1, 4:0, 5:0. The removal order is 4, 5, 0, 2, 3, 1, all six vertices, so the answer is false. That removal order is also a valid topological order of the graph.

Complexity. Time O(V + E): computing in-degrees scans every edge once, each vertex is enqueued at most once, and each edge is decremented once when its source is dequeued. Space O(V) for the in-degree array and the queue.

Edge cases and pitfalls