Unexpected Results When Using Depth-First Search for Cycle Detection in a Directed Graph in Python
I'm implementing a depth-first search (DFS) algorithm to detect cycles in a directed graph using Python, but I'm getting incorrect results when testing certain graphs. Specifically, my code returns that there are no cycles even when there should be. I’m using an adjacency list representation for the graph and maintaining a visited set along with a recursion stack to track the nodes currently in the recursion path. Below is the relevant part of my implementation: ```python class Graph: def __init__(self): self.graph = {} def add_edge(self, u, v): if u not in self.graph: self.graph[u] = [] self.graph[u].append(v) def is_cyclic_util(self, v, visited, rec_stack): visited.add(v) rec_stack.add(v) for neighbor in self.graph.get(v, []): if neighbor not in visited: if self.is_cyclic_util(neighbor, visited, rec_stack): return True elif neighbor in rec_stack: return True rec_stack.remove(v) return False def is_cyclic(self): visited = set() rec_stack = set() for node in self.graph: if node not in visited: if self.is_cyclic_util(node, visited, rec_stack): return True return False ``` When I run the following test: ```python g = Graph() g.add_edge(0, 1) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(1, 3) print(g.is_cyclic()) # Expected: True ``` It correctly identifies the cycle. However, when I test with a graph that looks like this: ```python g = Graph() g.add_edge(0, 1) g.add_edge(1, 2) g.add_edge(2, 3) g.add_edge(3, 1) print(g.is_cyclic()) # Expected: True ``` I get `False`, which is incorrect. I suspect that my recursion stack isn't being updated correctly, but I'm not sure where I’m going wrong. I’ve also tried adding debug statements, and they suggest that nodes are being marked as visited correctly but the recursion stack is not reflecting the current state accurately when revisiting nodes. I’m using Python 3.9. Can anyone point out what I might be missing or suggest any improvements to this cycle detection logic?