Detect a Cycle in a Graph
January 4, 2024
Problem #
Given a directed graph, write a function to detect whether the graph contains a cycle.
Example:
Input: Graph with edges [[0, 1], [1, 2], [2, 0]]
Output: True
(There is a cycle 0 > 1 > 2 > 0)
Solution #
 Algorithm: DepthFirst Search (DFS) Use DFS to detect the presence of a cycle in the graph. The idea is to traverse the graph along a particular path and if during the traversal we revisit a node, then there is a cycle in the graph.
Algorithm Steps: #
 Create an Adjacency List: Represent the graph using an adjacency list for efficient traversal.
 DFS with Recursion Stack: Use DFS to traverse the graph. Keep track of the nodes currently in the recursion stack.
 Check for Cycles: If a node is visited again and is in the current recursion stack, a cycle is detected.
 Explore All Nodes: Ensure all nodes are explored since the graph might be disconnected.

Python Code:
def isCyclic(graph): def dfs(vertex, visited, recStack): visited[vertex] = True recStack[vertex] = True for neighbour in graph[vertex]: if not visited[neighbour]: if dfs(neighbour, visited, recStack): return True elif recStack[neighbour]: return True recStack[vertex] = False return False visited = [False] * len(graph) recStack = [False] * len(graph) for node in range(len(graph)): if not visited[node]: if dfs(node, visited, recStack): return True return False # Example Usage graph = {0: [1], 1: [2], 2: [0]} print(isCyclic(graph))

Explanation:
 Create two boolean arrays
visited
andrecStack
.  Use DFS to traverse the graph.
 If an unvisited node leads to a node already in the recursion stack, a cycle exists.
 Return
True
if a cycle is found, otherwiseFalse
.
 Create two boolean arrays
Time Complexity: #
 O(V + E): Where V is the number of vertices and E is the number of edges. The DFS traversal takes O(V + E) time.
Space Complexity: #
 O(V): The space is used for the visited and recursion stack arrays.
This problem is fundamental in graph theory and algorithms, and understanding how to detect cycles in directed graphs is crucial for many applications, making it a suitable question for technical interviews at companies like Google, Amazon, Meta, and OpenAI.