Chapter 51 of 65

Cycle Detection in Graphs

On this page

Imagine three friends who each borrowed money from the next one.

Rahul is waiting for Priya to pay him back. Priya is waiting for Aman. And Aman is waiting for Rahul.

Rahul → waits for → Priya
Priya → waits for → Aman
Aman  → waits for → Rahul

Nobody can move first. Everyone is stuck in a loop.

In graph terms, this loop is called a cycle. Finding out whether a graph contains one is called cycle detection.

Cycle detection is the process of checking whether a graph contains a path that starts at some vertex and comes back to the same vertex without reusing an edge.

In the previous chapters you learned BFS and DFS. Cycle detection is one of the most important things you can build on top of them, and it shows up again and again in interviews.


What Is a Cycle?

A cycle is a path that starts and ends at the same vertex.

In an undirected graph:

A ─── B
|     |
D ─── C

We can go:

A → B → C → D → A

So this graph has a cycle.

In a directed graph, we must follow the arrows:

A → B
↑   ↓
D ← C

Following the arrows:

A → B → C → D → A

This is a directed cycle.

Now compare it with this graph:

A → B
↓   ↓
D → C

If you ignore the arrows, the shape looks like a square. But if you follow the arrows, you can never come back to where you started. So this directed graph has no cycle.

In a directed graph, a cycle must follow the direction of the edges.

Special Cases

A self-loop is an edge from a vertex to itself. It is a cycle of length 1.

A ──┐
↑   │
└───┘

In a directed graph, two edges in opposite directions also form a cycle:

A → B
B → A

But in an undirected graph, a single edge A ─ B is not a cycle. Walking from A to B and back uses the same edge twice.

A Useful Fact

A tree is a connected graph with no cycles, and a tree with V vertices always has exactly V - 1 edges.

So, for an undirected graph:

E ≥ V  →  the graph definitely has a cycle

The reverse is not true. A graph with fewer edges can still have a cycle if it is disconnected:

1 ─ 2       4
 \ /
  3

V = 4, E = 3, but 1 - 2 - 3 - 1 is a cycle

Why Do We Need Cycle Detection?

Cycles often mean something has gone wrong, or that a certain algorithm cannot be applied.

Situation

What a cycle means

Course prerequisites

Some courses can never be taken

Build systems (Maven, Gradle, npm)

Circular dependency, the build cannot finish

Operating systems

Processes waiting on each other, a deadlock

Spreadsheets

A circular reference, like A1 = B1 and B1 = A1

Network design

A redundant link that can be removed

Checking if a graph is a tree

A tree must not have any cycle

The next chapter, Topological Sort, only works on directed graphs that have no cycle. So cycle detection is the gatekeeper for it.


Undirected vs Directed: Two Different Problems

This is the most important idea in this chapter.

The technique for undirected graphs and the technique for directed graphs are different. Using the wrong one gives wrong answers.

Undirected Graph

Directed Graph

Track the parent of each vertex

Track which vertices are on the current DFS path

Cycle if we see a visited vertex that is not our parent

Cycle if we see a vertex that is still on the current path

Works with DFS or BFS

DFS with 3 states (or Kahn's algorithm from the next chapter)

Can also use Disjoint Set Union

Disjoint Set Union does not work

Let's go through both one by one.


Undirected Graph: The Parent Idea

In DFS, we mark vertices as visited. So a natural first thought is:

If I reach a vertex that is already visited,
there must be a cycle.

This is almost right, but there is a catch.

In an undirected graph, the edge 0 ─ 1 is stored in both adjacency lists:

0 : [1]
1 : [0]

So when DFS goes from 0 to 1, it looks at the neighbors of 1 and immediately sees 0, which is already visited.

That is not a cycle. It is just the same edge we used to arrive.

The fix is to remember the vertex we came from, called the parent:

For each neighbor of the current node:

    not visited              → explore it (current node becomes its parent)
    visited and == parent    → ignore, it is the edge we came from
    visited and != parent    → CYCLE

In an undirected graph, a cycle exists if DFS reaches an already visited vertex that is not the parent of the current vertex.


Step-by-Step Example (Undirected)

Consider this graph:

0 ─── 1 ─── 2
      |     |
      3 ────┘
      |
      4

Edges: 0-1, 1-2, 2-3, 3-1, 3-4.

The adjacency list (in the order the edges are added) is:

0 : [1]
1 : [0, 2, 3]
2 : [1, 3]
3 : [2, 1, 4]
4 : [3]

Now run DFS from 0:

dfs(0, parent = -1)
  neighbor 1 → not visited → go deeper

dfs(1, parent = 0)
  neighbor 0 → visited, but it is the parent → ignore
  neighbor 2 → not visited → go deeper

dfs(2, parent = 1)
  neighbor 1 → visited, but it is the parent → ignore
  neighbor 3 → not visited → go deeper

dfs(3, parent = 2)
  neighbor 2 → visited, but it is the parent → ignore
  neighbor 1 → visited, and parent is 2, not 1 → CYCLE!

DFS reached 1 through a different route (1 → 2 → 3 → 1). That second route is exactly the cycle.


Cycle Detection in an Undirected Graph Using DFS

The algorithm:

hasCycle(graph):

    for every vertex v:
        if v is not visited:
            if dfs(v, -1) finds a cycle:
                return true

    return false


dfs(node, parent):

    mark node as visited

    for each neighbor of node:

        if neighbor is not visited:
            if dfs(neighbor, node) finds a cycle:
                return true

        else if neighbor != parent:
            return true

    return false

Here is the complete Java program. Graph 1 is the graph from the step-by-step example, Graph 2 is a tree, and Graph 3 is a disconnected graph whose cycle is only in the second part.

import java.util.ArrayList;

class Main {

    static ArrayList<ArrayList<Integer>> createGraph(int vertices) {

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        return graph;
    }

    static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    static boolean dfs(
        int node,
        int parent,
        ArrayList<ArrayList<Integer>> graph,
        boolean[] visited
    ) {

        visited[node] = true;

        for (int neighbor : graph.get(node)) {

            if (!visited[neighbor]) {

                if (dfs(neighbor, node, graph, visited)) {
                    return true;
                }

            } else if (neighbor != parent) {

                // visited, and not the vertex we came from
                return true;
            }
        }

        return false;
    }

    static boolean hasCycle(ArrayList<ArrayList<Integer>> graph) {

        boolean[] visited = new boolean[graph.size()];

        // check every component
        for (int i = 0; i < graph.size(); i++) {

            if (!visited[i]) {

                if (dfs(i, -1, graph, visited)) {
                    return true;
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {

        // Graph 1: 1 - 2 - 3 - 1 forms a cycle
        ArrayList<ArrayList<Integer>> g1 = createGraph(5);
        addEdge(g1, 0, 1);
        addEdge(g1, 1, 2);
        addEdge(g1, 2, 3);
        addEdge(g1, 3, 1);
        addEdge(g1, 3, 4);

        // Graph 2: a tree, no cycle
        ArrayList<ArrayList<Integer>> g2 = createGraph(5);
        addEdge(g2, 0, 1);
        addEdge(g2, 0, 2);
        addEdge(g2, 1, 3);
        addEdge(g2, 1, 4);

        // Graph 3: disconnected, cycle only in the second part
        ArrayList<ArrayList<Integer>> g3 = createGraph(5);
        addEdge(g3, 0, 1);
        addEdge(g3, 2, 3);
        addEdge(g3, 3, 4);
        addEdge(g3, 4, 2);

        System.out.println("Graph 1 has cycle: " + hasCycle(g1));
        System.out.println("Graph 2 has cycle: " + hasCycle(g2));
        System.out.println("Graph 3 has cycle: " + hasCycle(g3));
    }
}

Output:

Graph 1 has cycle: true
Graph 2 has cycle: false
Graph 3 has cycle: true

Don't Forget Disconnected Graphs

Look at Graph 3 again:

0 ─ 1        2 ─ 3
              \ /
               4

If we only run dfs(0, -1), we explore 0 and 1, find no cycle, and stop. We would never see the cycle 2 → 3 → 4 → 2.

That is why hasCycle() loops over every vertex and starts a new DFS from each unvisited one, exactly like counting connected components in the DFS chapter.

Always start a traversal from every unvisited vertex. A cycle can hide in any component.


Cycle Detection in an Undirected Graph Using BFS

The same parent idea works with BFS. The only change is that the queue must store the parent along with each vertex.

We store pairs:

{node, parent}

When we look at a neighbor:

not visited           → mark visited, add {neighbor, node} to the queue
visited, != parent    → CYCLE

Complete program:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

class Main {

    static ArrayList<ArrayList<Integer>> createGraph(int vertices) {

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        return graph;
    }

    static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    static boolean bfs(
        int start,
        ArrayList<ArrayList<Integer>> graph,
        boolean[] visited
    ) {

        // each entry is {node, parent}
        Queue<int[]> queue = new ArrayDeque<>();

        visited[start] = true;
        queue.add(new int[] {start, -1});

        while (!queue.isEmpty()) {

            int[] current = queue.poll();
            int node = current[0];
            int parent = current[1];

            for (int neighbor : graph.get(node)) {

                if (!visited[neighbor]) {

                    visited[neighbor] = true;
                    queue.add(new int[] {neighbor, node});

                } else if (neighbor != parent) {

                    return true;
                }
            }
        }

        return false;
    }

    static boolean hasCycle(ArrayList<ArrayList<Integer>> graph) {

        boolean[] visited = new boolean[graph.size()];

        for (int i = 0; i < graph.size(); i++) {

            if (!visited[i] && bfs(i, graph, visited)) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {

        ArrayList<ArrayList<Integer>> g1 = createGraph(5);
        addEdge(g1, 0, 1);
        addEdge(g1, 1, 2);
        addEdge(g1, 2, 3);
        addEdge(g1, 3, 1);
        addEdge(g1, 3, 4);

        ArrayList<ArrayList<Integer>> g2 = createGraph(5);
        addEdge(g2, 0, 1);
        addEdge(g2, 0, 2);
        addEdge(g2, 1, 3);
        addEdge(g2, 1, 4);

        System.out.println("Graph 1 has cycle: " + hasCycle(g1));
        System.out.println("Graph 2 has cycle: " + hasCycle(g2));
    }
}

Output:

Graph 1 has cycle: true
Graph 2 has cycle: false

Why does this work? In BFS, a vertex is marked visited when it is first discovered. If we later find another edge leading to an already discovered vertex (other than the one we came from), there are two different routes to that vertex, which together form a cycle.

Both versions take O(V + E) time. Choose whichever you find easier. DFS is more common in interviews.


Directed Graph: Why the Parent Trick Fails

Now let's move to directed graphs.

Consider this "diamond" graph:

      0
     / \
    ↓   ↓
    1   2
     \ /
      ↓
      3

Edges: 0 → 1, 0 → 2, 1 → 3, 2 → 3

Is there a cycle? No. All arrows point downward, so you can never come back up.

But vertex 3 can be reached in two ways: 0 → 1 → 3 and 0 → 2 → 3.

A simple "visited means cycle" check gets fooled:

import java.util.ArrayList;

class Main {

    // WRONG for directed graphs: a plain visited[] check
    static boolean wrongDfs(
        int node,
        ArrayList<ArrayList<Integer>> graph,
        boolean[] visited
    ) {

        visited[node] = true;

        for (int neighbor : graph.get(node)) {

            if (visited[neighbor]) {
                return true;
            }

            if (wrongDfs(neighbor, graph, visited)) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {

        ArrayList<ArrayList<Integer>> g = new ArrayList<>();

        for (int i = 0; i < 4; i++) {
            g.add(new ArrayList<>());
        }

        g.get(0).add(1);
        g.get(0).add(2);
        g.get(1).add(3);
        g.get(2).add(3);

        System.out.println("Diamond has cycle: " + wrongDfs(0, g, new boolean[4]));
    }
}

Output:

Diamond has cycle: true

This is wrong.

What happened?

dfs(0) → dfs(1) → dfs(3)       3 is now visited, finished
back to 0 → dfs(2)
  neighbor 3 is visited → "cycle"   ✗ wrong

When DFS reached 3 the second time, 3 was already completely finished. Reaching a finished vertex again does not mean we can get back to where we are now.

A parent check doesn't help either, because in a directed graph, the edge u → v is stored only once. There is no "edge back to the parent" to ignore.

In a directed graph, reaching a visited vertex is only a cycle if that vertex is still on the current DFS path.


The Three-State (Three-Color) Method

To know whether a vertex is "on the current path" or "already finished", we give each vertex one of three states:

State

Also called

Meaning

UNVISITED (0)

White

Not seen yet

VISITING (1)

Gray

DFS has entered it but not finished it. It is on the current path (in the recursion stack).

DONE (2)

Black

DFS has finished it and all its descendants

The rules:

Enter a vertex          → mark it VISITING

Look at a neighbor:
    UNVISITED           → explore it
    VISITING            → CYCLE (we came back to our own path)
    DONE                → ignore (already fully explored, no cycle through it)

Leave a vertex          → mark it DONE

An edge that points to a VISITING vertex is called a back edge. It points from a vertex back to one of its own ancestors in the DFS.

A directed graph has a cycle if and only if DFS finds a back edge.

Some people implement this with two boolean arrays instead of one state array:

visited[]     → has DFS ever entered this vertex?
inPath[]      → is this vertex in the current recursion stack?

It is the same idea. visited = true, inPath = true means VISITING, and visited = true, inPath = false means DONE.


Step-by-Step Example (Directed)

Graph with a cycle:

0 → 1 → 2
    ↑   ↓
    └── 3

Edges: 0 → 1, 1 → 2, 2 → 3, 3 → 1

DFS from 0:

dfs(0)  state[0] = VISITING        path: 0
dfs(1)  state[1] = VISITING        path: 0 → 1
dfs(2)  state[2] = VISITING        path: 0 → 1 → 2
dfs(3)  state[3] = VISITING        path: 0 → 1 → 2 → 3

  neighbor 1 has state VISITING → back edge 3 → 1 → CYCLE

Now the diamond graph (no cycle):

dfs(0)  VISITING                   path: 0
dfs(1)  VISITING                   path: 0 → 1
dfs(3)  VISITING                   path: 0 → 1 → 3
        3 has no neighbors → state[3] = DONE
        back in 1 → state[1] = DONE
back in 0
dfs(2)  VISITING                   path: 0 → 2
        neighbor 3 has state DONE → ignore
        state[2] = DONE
state[0] = DONE

No back edge → NO CYCLE

The three states correctly tell the difference between "I came back to my own path" and "I reached something that was already finished".


Cycle Detection in a Directed Graph Using DFS

import java.util.ArrayList;

class Main {

    static final int UNVISITED = 0;
    static final int VISITING = 1;   // on the current DFS path
    static final int DONE = 2;       // fully explored

    static ArrayList<ArrayList<Integer>> createGraph(int vertices) {

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        return graph;
    }

    static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v) {
        graph.get(u).add(v);   // directed: only u -> v
    }

    static boolean dfs(
        int node,
        ArrayList<ArrayList<Integer>> graph,
        int[] state
    ) {

        state[node] = VISITING;

        for (int neighbor : graph.get(node)) {

            if (state[neighbor] == VISITING) {

                // back edge: neighbor is still on the current path
                return true;
            }

            if (state[neighbor] == UNVISITED) {

                if (dfs(neighbor, graph, state)) {
                    return true;
                }
            }

            // state == DONE: already fully explored, safe to skip
        }

        state[node] = DONE;

        return false;
    }

    static boolean hasCycle(ArrayList<ArrayList<Integer>> graph) {

        int[] state = new int[graph.size()];

        for (int i = 0; i < graph.size(); i++) {

            if (state[i] == UNVISITED && dfs(i, graph, state)) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {

        // Graph 1: 1 -> 2 -> 3 -> 1 is a cycle
        ArrayList<ArrayList<Integer>> g1 = createGraph(4);
        addEdge(g1, 0, 1);
        addEdge(g1, 1, 2);
        addEdge(g1, 2, 3);
        addEdge(g1, 3, 1);

        // Graph 2: diamond shape, 3 is reached twice but no cycle
        ArrayList<ArrayList<Integer>> g2 = createGraph(4);
        addEdge(g2, 0, 1);
        addEdge(g2, 0, 2);
        addEdge(g2, 1, 3);
        addEdge(g2, 2, 3);

        System.out.println("Graph 1 has cycle: " + hasCycle(g1));
        System.out.println("Graph 2 has cycle: " + hasCycle(g2));
    }
}

Output:

Graph 1 has cycle: true
Graph 2 has cycle: false

The most important line is the last one inside dfs():

state[node] = DONE;

When DFS finishes a vertex, it is removed from the current path. If you forget this line, every visited vertex stays VISITING forever, and the diamond graph would wrongly report a cycle again.


Printing the Cycle

Sometimes an interviewer asks you to return the actual cycle, not just true or false.

We can do this by storing the parent of each vertex in the DFS tree. When we find a back edge node → neighbor, the cycle is:

neighbor → ... → node → neighbor

We get the middle part by walking back from node using parent[] until we reach neighbor.

import java.util.ArrayList;
import java.util.Collections;

class Main {

    static int[] state;
    static int[] parent;
    static int cycleStart = -1;
    static int cycleEnd = -1;

    static boolean dfs(int node, ArrayList<ArrayList<Integer>> graph) {

        state[node] = 1;

        for (int neighbor : graph.get(node)) {

            if (state[neighbor] == 0) {

                parent[neighbor] = node;

                if (dfs(neighbor, graph)) {
                    return true;
                }

            } else if (state[neighbor] == 1) {

                // back edge node -> neighbor closes the cycle
                cycleStart = neighbor;
                cycleEnd = node;
                return true;
            }
        }

        state[node] = 2;

        return false;
    }

    public static void main(String[] args) {

        int vertices = 5;

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        graph.get(0).add(1);
        graph.get(1).add(2);
        graph.get(2).add(3);
        graph.get(3).add(4);
        graph.get(4).add(2);   // closes the cycle 2 -> 3 -> 4 -> 2

        state = new int[vertices];
        parent = new int[vertices];

        for (int i = 0; i < vertices; i++) {

            if (state[i] == 0 && dfs(i, graph)) {
                break;
            }
        }

        if (cycleStart == -1) {
            System.out.println("No cycle");
            return;
        }

        // walk back from cycleEnd to cycleStart using parent[]
        ArrayList<Integer> cycle = new ArrayList<>();
        cycle.add(cycleStart);

        for (int v = cycleEnd; v != cycleStart; v = parent[v]) {
            cycle.add(v);
        }

        cycle.add(cycleStart);
        Collections.reverse(cycle);

        StringBuilder sb = new StringBuilder("Cycle found: ");

        for (int i = 0; i < cycle.size(); i++) {

            sb.append(cycle.get(i));

            if (i < cycle.size() - 1) {
                sb.append(" -> ");
            }
        }

        System.out.println(sb);
    }
}

Output:

Cycle found: 2 -> 3 -> 4 -> 2

Here, DFS goes 0 → 1 → 2 → 3 → 4, then finds the back edge 4 → 2. Walking back from 4 gives 4, 3 and then 2, which after reversing becomes the cycle.

The same parent-walking trick works for undirected graphs too.


Other Ways to Detect Cycles

DFS is not the only option. You will meet two more methods in the next chapters.

Kahn's Algorithm (Directed Graphs)

In the next chapter, Topological Sort, you will learn Kahn's algorithm. It repeatedly removes vertices that have no incoming edges.

If the algorithm gets stuck before removing every vertex, the remaining vertices must be part of a cycle. So Kahn's algorithm is a BFS-style way to detect cycles in directed graphs.

Disjoint Set Union (Undirected Graphs)

In the Disjoint Set Union chapter, you will see a structure that keeps track of which vertices are already connected.

The idea is simple: process edges one by one. If an edge connects two vertices that are already connected, that edge creates a cycle.

This method works only for undirected graphs, and it is the heart of Kruskal's algorithm for minimum spanning trees.

Method

Undirected

Directed

DFS + parent

Yes

No

BFS + parent

Yes

No

DFS + three states

Not used (the parent check is the right tool)

Yes

Kahn's algorithm

No

Yes

Disjoint Set Union

Yes

No


Time and Space Complexity

Every method in this chapter is a normal BFS or DFS with a small extra check, so the cost is the same as a traversal.

With an adjacency list:

Time  → O(V + E)
Space → O(V)

Each vertex is visited once and each edge is looked at a constant number of times (twice for undirected graphs, once for directed graphs).

The O(V) space is for the visited[] or state[] array, the parent[] array, and the recursion stack or queue.

With an adjacency matrix, the time becomes O(V²), just like plain DFS and BFS.


Common Mistakes

1. Using the undirected method on a directed graph

A plain visited[] check (or a parent check) reports false cycles in graphs like the diamond. For directed graphs, always use the three states.

2. Forgetting the parent check in an undirected graph

Without it, every single edge looks like a cycle, because 0 ─ 1 appears in both adjacency lists.

3. Forgetting to mark a vertex DONE

In the directed version, if a vertex stays VISITING after DFS leaves it, later paths that reach it will wrongly report a cycle.

4. Only starting from vertex 0

If the graph is disconnected (or in a directed graph, some vertices cannot be reached from 0), you will miss cycles. Loop over all vertices.

5. Parallel edges in an undirected graph

If the input can contain the same edge twice (0 ─ 1 and 0 ─ 1 again), those two edges form a cycle, but the parent check ignores both. In such cases, track the edge index you came from instead of the parent vertex. Most interview problems guarantee no duplicate edges, but it is worth asking.

6. Deep recursion

For very large graphs that look like a long chain, recursive DFS can cause a StackOverflowError in Java. In that case, use the BFS version for undirected graphs, or Kahn's algorithm for directed graphs.


Practice Problems

  • Detect Cycle in an Undirected Graph (GeeksforGeeks), DFS or BFS with parent

  • Detect Cycle in a Directed Graph (GeeksforGeeks), DFS with three states

  • Course Schedule (LeetCode 207), can all courses be finished? Same as "does the directed graph have a cycle?"

  • Graph Valid Tree (LeetCode 261), connected and no cycle

  • Find Eventual Safe States (LeetCode 802), vertices that cannot reach any cycle, a nice use of the three states

  • Redundant Connection (LeetCode 684), find the edge that creates a cycle (try it again after the DSU chapter)


Interview Tips

  • The first thing to ask: "Is the graph directed or undirected?" The answer decides the whole approach.

  • Also ask whether the graph can be disconnected and whether duplicate edges or self-loops are possible.

  • When a problem talks about dependencies, prerequisites or ordering, it is almost always secretly asking "is there a cycle in this directed graph?"

  • Be ready to explain why the parent check is not enough for directed graphs. The diamond example is the quickest way to show it.


The Main Idea

A cycle is a path that starts and ends at the same vertex. Detecting it is a small extension of DFS or BFS.

For undirected graphs:

Visited neighbor that is NOT the parent → cycle

For directed graphs:

Neighbor that is still VISITING (on the current path) → cycle
Neighbor that is DONE                                 → no problem

Both run in:

Time  → O(V + E)
Space → O(V)

And remember to run the check from every unvisited vertex, so no component is missed.

Undirected graph: watch out for the parent. Directed graph: watch out for the current path.

In the next chapter, you will use this knowledge to put the vertices of a cycle-free directed graph into a valid order using Topological Sort.