Detect Cycle in Directed Graph using BFS DFS Algo
Problem Statement
Given a directed graph with V vertices and E edges, detect whether the graph contains a cycle.
Example:
- Input:
V = 4, Edges = [[0,1],[1,2],[2,3],[3,1]] - Output:
true(cycle: 1 → 2 → 3 → 1)
Noob-Friendly Explanation
Imagine you have a to-do list where some tasks depend on others (like "cook food" depends on "buy groceries"). The arrows show what must come first. A cycle means there's a circular dependency — Task A needs B, B needs C, and C needs A. Nobody can start! That's the cycle we want to detect.
Approach 1: Brute Force (DFS with Recursion Stack)
Intuition
Do a DFS traversal. Keep track of vertices currently in the recursion stack (the current path). If we visit a vertex that's already in the current path, we've found a cycle. This is different from just "visited" — a visited node from a different path is fine, but visiting a node in the same path means a loop.
Algorithm
- Build an adjacency list.
- Maintain two arrays:
visited[]andrecStack[]. - For each unvisited vertex, start DFS.
- In DFS, mark the vertex as visited and add to recStack.
- Visit all neighbors — if a neighbor is in recStack, return true (cycle found).
- After processing all neighbors, remove the vertex from recStack.
import java.util.ArrayList;
import java.util.List;
public class CycleDirectedDFS {
static boolean dfs(List<List<Integer>> adj, boolean[] visited, boolean[] recStack, int node) {
visited[node] = true;
recStack[node] = true;
for (int neighbor : adj.get(node)) {
// If neighbor is in current recursion stack, cycle found
if (recStack[neighbor]) {
return true;
}
// If not visited, recurse
if (!visited[neighbor]) {
if (dfs(adj, visited, recStack, neighbor)) {
return true;
}
}
}
recStack[node] = false; // backtrack
return false;
}
public static boolean hasCycle(int V, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]); // directed edge
}
boolean[] visited = new boolean[V];
boolean[] recStack = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (dfs(adj, visited, recStack, i)) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
int V = 4;
int[][] edges = {{0,1},{1,2},{2,3},{3,1}};
System.out.println(hasCycle(V, edges)); // true
}
}Complexity Analysis
- Time Complexity: O(V + E) — each vertex and edge is processed once.
- Space Complexity: O(V) — for visited, recStack arrays and recursion stack.
Approach 2: Optimal (BFS — Kahn's Algorithm)
Intuition
Use Kahn's Algorithm (topological sort via BFS). The idea: if we can process all vertices in topological order, there's no cycle. If some vertices can never be processed (because they're stuck in a cycle), we have a cycle.
Count how many vertices have in-degree 0 (no incoming edges). Process them, reduce in-degrees of their neighbors, and repeat. If the total processed vertices is less than V, there's a cycle.
Algorithm
- Build adjacency list and compute in-degree for each vertex.
- Add all vertices with in-degree 0 to a queue.
- Process the queue: dequeue a vertex, reduce in-degree of its neighbors.
- If a neighbor's in-degree becomes 0, enqueue it.
- Count processed vertices. If count < V, a cycle exists.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class CycleDirectedBFS {
public static boolean hasCycle(int V, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[V];
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
inDegree[edge[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
int processedCount = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
processedCount++;
for (int neighbor : adj.get(node)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.add(neighbor);
}
}
}
// If not all vertices were processed, there's a cycle
return processedCount != V;
}
public static void main(String[] args) {
int V = 4;
int[][] edges = {{0,1},{1,2},{2,3},{3,1}};
System.out.println(hasCycle(V, edges)); // true
}
}Complexity Analysis
- Time Complexity: O(V + E) — each vertex and edge is processed once.
- Space Complexity: O(V) — for the in-degree array and the queue.