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 → RahulNobody 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 ─── CWe can go:
A → B → C → D → ASo this graph has a cycle.
In a directed graph, we must follow the arrows:
A → B
↑ ↓
D ← CFollowing the arrows:
A → B → C → D → AThis is a directed cycle.
Now compare it with this graph:
A → B
↓ ↓
D → CIf 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 → ABut 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 cycleThe 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 cycleWhy 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 |
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 → CYCLEIn 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 ────┘
|
4Edges: 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 falseHere 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: trueDon't Forget Disconnected Graphs
Look at Graph 3 again:
0 ─ 1 2 ─ 3
\ /
4If 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 → CYCLEComplete 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: falseWhy 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 → 3Is 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: trueThis 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" ✗ wrongWhen 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 |
|---|---|---|
| White | Not seen yet |
| Gray | DFS has entered it but not finished it. It is on the current path (in the recursion stack). |
| 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 DONEAn 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 → 1DFS 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 → CYCLENow 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 CYCLEThe 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: falseThe 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 → neighborWe 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 -> 2Here, 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 → cycleFor directed graphs:
Neighbor that is still VISITING (on the current path) → cycle
Neighbor that is DONE → no problemBoth 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.