PROBLEM DESCRIPTION
Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check whether it contains any cycle or not.
SOLUTION
APPROACH 1 - USING DFS (STACK OVERFLOW FOR LARGE #NODES)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
boolean[] visited = new boolean[V];
// track nodes in the current recursion path
boolean[] path = new boolean[V];
// Iterate over all vertices
for (int i = 0; i < V; i++) {
// If a cycle is found, return true
if (isCyclicHelper(V, adj, visited, path, i)) {
return true;
}
}
// No cycle found in any DFS traversal, return false
return false;
}
public boolean isCyclicHelper(int V, ArrayList<ArrayList<Integer>> adj, boolean[] visited, boolean[] path, int i) {
// If the node is already in the current path, a cycle is detected
if (path[i]) {
return true;
}
// If the node is already visited, no need to explore again, return false
if (visited[i]) {
return false;
}
// Mark the current node as visited
visited[i] = true;
// Add the current node to the recursion path
path[i] = true;
// Check all adjacent vertices
for (int neighbor : adj.get(i)) {
// If any adjacent node causes a cycle, return true
if (isCyclicHelper(V, adj, visited, path, neighbor)) {
return true;
}
}
// Remove the current node from the recursion path (backtrack)
path[i] = false;
// No cycle detected
return false;
}
}
APPROACH 2 - USING INDEGREE (ACCEPTED)
We can solve this by using Kahn's Algorithm, which is a BFS-based approach to check for cycles in a directed graph.
The idea is to track the in-degrees of all vertices, which represent how many edges point to each vertex.
We first identify vertices with zero in-degrees (i.e., no dependencies) and add them to a queue.
As we process these vertices, we reduce the in-degrees of their neighbors. If a neighbor’s in-degree becomes zero, we add it to the queue as well. If all vertices are processed without finding any vertex with a non-zero in-degree at the end, the graph is acyclic.
However, if any vertex still has a non-zero in-degree after processing, it means there is a cycle, as some vertices are dependent on each other in a circular way.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
// Kahn's Algorithm (BFS-based topological sorting)
public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
//in-degrees for all vertices
int[] indegree = new int[V];
for (int i = 0; i < V; i++) {
for (Integer j : adj.get(i)) {
indegree[j]++;
}
}
Queue<Integer> q = new LinkedList<>();
// add vertices with zero in-degree
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
q.add(i);
}
}
// keep removing that node from the queue
// assume is it removed from the graph
// that means, indegree will reduce for all its adjacent nodes (neighbors). If it becomes 0, add that neighbor
// the expectation is that all nodes should be added eventually if the graph has no cycle
while (!q.isEmpty()) {
// Dequeue a vertex
int x = q.poll();
// Get all neighbors of the dequeued vertex
ArrayList<Integer> neighbors = adj.get(x);
// Decrease the in-degree of all adjacent vertices
for (Integer n : neighbors) {
indegree[n]--;
// If in-degree of a neighbor becomes zero, add it to the queue
if (indegree[n] == 0) {
q.add(n);
}
}
}
// Check if there are any vertices with non-zero in-degree
// If any vertex still has a non-zero in-degree, it means a cycle exists
for (int i = 0; i < V; i++) {
if (indegree[i] != 0)
return true;
}
// If all vertices have zero in-degree, no cycle exists
return false;
}
}