Cycle Detection in Directed Graph

February 6, 2024

Problem Statement #

Given a directed graph with n nodes labeled from 0 to n-1, and a list of edges where edges[i] = [ai, bi] represents a directed edge from node ai to node bi, determine if the graph contains a cycle. A cycle occurs if a node can be visited more than once by following the directed edges. Return true if the graph contains at least one cycle, otherwise return false.

Solution Approach #

The solution involves using Depth-First Search (DFS) to explore the graph from each unvisited node, keeping track of nodes currently in the recursion stack. If we revisit a node that is already in the recursion stack, a cycle exists.

Algorithm Steps #

1. Create an adjacency list from the edges to represent the graph.
2. Initialize a visited set to keep track of visited nodes and a recursion stack set to keep track of nodes in the current DFS path.
3. Iterate over each node and, if it’s not visited, start a DFS from it.
4. In the DFS, mark the node as visited and add it to the recursion stack. Then, visit all its neighbors. If any neighbor is already in the recursion stack, a cycle is found.
5. After visiting all neighbors, remove the node from the recursion stack.
6. If no cycle is found after exploring all nodes, return false.

Code (Python) #

def cycleDetection(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)

    visited = set()
    recStack = set()

    def dfs(node):
        if node in recStack:
            return True
        if node in visited:
            return False
        visited.add(node)
        recStack.add(node)
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True
        recStack.remove(node)
        return False

    for node in range(n):
        if node not in visited:
            if dfs(node):
                return True
    return False

# Example usage
print(cycleDetection(4, [[0, 1], [1, 2], [2, 3], [3, 1]]))  # Output: True

Time Complexity #

O(V + E), where V is the number of vertices and E is the number of edges in the graph. Each node and edge is visited at most once.

Space Complexity #

O(V + E), for storing the graph, visited set, and recursion stack. In the worst case, the space complexity can approach O(V + E) when the graph is densely connected.