Detect a Cycle in a Directed Graph

96.2k
0

Given a directed graph with V vertices represented by an adjacency list, determine whether any directed cycle exists.

A directed cycle exists when traversal follows edge directions and returns to a vertex already present in the same active path. The graph can be disconnected, so every component must be checked.

Example 1

Input: V = 4, adj = [[1],[2],[0,3],[]]

Output: true

Explanation: Directed edges 0 -> 1 -> 2 -> 0 form a cycle.

Example 2

Input: V = 4, adj = [[1,2],[2],[3],[]]

Output: false

Explanation: All directed paths move forward without returning to an active vertex.

Approach 1

Depth First Search maintains two states: vertices visited during the complete traversal and vertices present in the current active recursion path. Reaching a vertex already present in the active path indicates a back edge and confirms a directed cycle.

After all outgoing edges of a vertex are processed, removal from the active path allows later DFS branches to visit the vertex without incorrectly reporting a cycle.

Algorithm

  • Initialize visited and pathVisited arrays of size V, separating globally processed vertices from vertices in the active DFS path.

  • Traverse every vertex and start DFS from each unvisited vertex, ensuring that all disconnected components are examined.

  • Mark the current vertex in both arrays, recording global visitation and active-path membership.

  • Examine every outgoing neighbor of the current vertex to inspect all possible directed paths.

  • For an unvisited neighbor, continue DFS and immediately propagate true when a deeper recursive call detects a cycle.

  • Return true when a neighbor is already marked in pathVisited, as an edge to an active-path vertex confirms a directed cycle.

  • Remove the current vertex from pathVisited after processing all neighbors, and return false when every component finishes without detecting a cycle.

Dry Run

detect cycle 1

detect cycle 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Detects a back edge using DFS.
bool dfs(int node, vector<int>& visited, vector<int>& pathVisited, vector<vector<int>>& adj) {
// Mark the node as visited.
visited[node] = 1;
// Mark the node in the current DFS path.
pathVisited[node] = 1;
// Explore all outgoing edges.
for (int neighbor : adj[node]) {
// Visit the neighbor if it is not visited.
if (!visited[neighbor]) {
// If a cycle is found deeper, return true.
if (dfs(neighbor, visited, pathVisited, adj)) {
return true;
}
}
// If neighbor is in the current path, a cycle exists.
else if (pathVisited[neighbor]) {
return true;
}
}
// Remove current vertex from active DFS path.
pathVisited[node] = 0;
// No cycle found from this path.
return false;
}
public:
// Detects a cycle in a directed graph.
bool isCyclic(int vertices, vector<vector<int>>& adj) {
vector<int> visited(vertices, 0);
vector<int> pathVisited(vertices, 0);
// Start DFS from every unvisited vertex.
for (int node = 0; node < vertices; node++) {
// Only unvisited nodes can start a new DFS.
if (!visited[node]) {
// If any DFS finds a cycle, return true.
if (dfs(node, visited, pathVisited, adj)) {
return true;
}
}
}
// No back edge exists in any component.
return false;
}
};
// Driver code.
int main() {
int vertices = 4;
vector<vector<int>> adj = {
{1},
{2},
{0, 3},
{}
};
Solution sol;
cout << (sol.isCyclic(vertices, adj) ? "true" : "false");
return 0;
}

Complexity Analysis

Time Complexity: O(V+E), where V and E are the numbers of vertices and directed edges; DFS processes every vertex and edge once.

Space Complexity: O(V), where both visited arrays and the recursive DFS stack store a number of entries proportional to V.

Approach 2

Kahn’s Algorithm applies topological-sorting logic to detect a cycle. In a directed acyclic graph, repeated removal of vertices having indegree 0 eventually processes every vertex.

Vertices belonging to a directed cycle never reach indegree 0 because every cycle vertex retains an incoming edge. A processed count smaller than V therefore confirms a cycle.

Algorithm

  • Initialize an indegree array of size V, where each entry stores the number of incoming edges for a vertex.

  • Scan every directed edge and increment the indegree of the destination vertex, preparing the dependency count required by Kahn’s Algorithm.

  • Add all vertices having indegree 0 to a queue, since such vertices have no unresolved incoming dependencies.

  • Initialize processedCount to 0 and continue processing while the queue contains vertices.

  • Remove the front vertex and increment processedCount, recording successful removal from the topological ordering.

  • Decrease the indegree of every outgoing neighbor and add a neighbor to the queue when the indegree becomes 0.

  • Return true when processedCount differs from V; otherwise, return false because all vertices formed a valid topological order.

Dry Run

detect cycle 2

detect cycle 2

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Detects a cycle using Kahn's Algorithm.
bool isCyclic(int vertices, vector<vector<int>>& adj) {
vector<int> indegree(vertices, 0);
// Compute indegree for every vertex.
for (int node = 0; node < vertices; node++) {
for (int neighbor : adj[node]) {
indegree[neighbor]++;
}
}
queue<int> q;
// Add all vertices with zero indegree.
for (int node = 0; node < vertices; node++) {
// Zero indegree means this node can be processed first.
if (indegree[node] == 0) {
q.push(node);
}
}
int processed = 0;
// Remove zero-indegree vertices one by one.
while (!q.empty()) {
int node = q.front();
q.pop();
// Count this node as processed.
processed++;
// Reduce indegree of outgoing neighbors.
for (int neighbor : adj[node]) {
indegree[neighbor]--;
// If indegree becomes zero, add it to the queue.
if (indegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
// If some vertices remain unprocessed, a cycle exists.
return processed != vertices;
}
};
// Driver code.
int main() {
int vertices = 4;
vector<vector<int>> adj = {
{1, 2},
{2},
{3},
{}
};
Solution sol;
cout << (sol.isCyclic(vertices, adj) ? "true" : "false");
return 0;
}

Complexity Analysis

Time Complexity: O(V+E), where V and E are the numbers of vertices and directed edges; every vertex and edge is processed once.

Space Complexity: O(V), where the indegree array and queue can each store up to V vertices.

Interview follow-up Questions

Reaching a vertex already in the active DFS path means edge directions have formed a closed path.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

Design a disjoint set, also called a union-find data structure, for N nodes numbered from 1 to N . Initially, every node belongs to a separate set. Support the following operations: DisjointSet(int...

89.1k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weig...

96.1k
Graph

Network Delay Time Using Dijkstra's Algorithm

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2 Explanation: Nodes 1 and 3 receive the signal after 1 time unit. Node 4 receives the signal through node 3 after 2 time units. Input...

81.2k
Comments0