Hi @Amit_Adiraju_Narasim,
The separate stack and visited lists serve different purposes in the cycle detection algorithm:
- Visited List (
visited):
- The
visited list keeps track of nodes that have been visited during the entire algorithm execution.
- It helps prevent infinite recursion by ensuring that the algorithm does not revisit nodes that have already been explored.
- If a node is visited in a previous recursive call but is not currently on the call stack, it means there is no cycle involving that node.
- This list helps avoid redundant work by preventing revisits to nodes that have already been explored.
- Stack (
my_stack):
- The
my_stack list maintains a record of nodes that are part of the current recursion stack.
- It helps detect cycles by identifying nodes that are encountered again within the same recursion call.
- If a node is encountered again while it is already present on the current recursion stack, it indicates the presence of a cycle.
- This stack keeps track of nodes currently being explored in the depth-first search (DFS) traversal.
Separating these lists allows the algorithm to differentiate between nodes that have been visited in previous iterations and nodes that are currently part of the recursion stack. This distinction is crucial for accurately detecting cycles in a graph.
let’s look at a simple example of a graph to illustrate how the provided solution works. We’ll create a directed graph with some nodes and edges, and then apply the cycle detection algorithm on it.
Consider the following graph:
0 <--- 3
| / ^
| / |
v / |
1 ---> 2
In this graph:
- Node 0 has an edge to node 1.
- Node 1 has an edge to nodes 2 and 3.
- Node 2 has an edge back to node 1.
- Node 3 has an edge back to node 0.
Now, let’s apply the cycle detection algorithm on this graph:
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def detect_cycle(graph):
visited = [False] * graph.V
my_stack = [False] * graph.V
for node in range(graph.V):
if detect_cycle_recursive(graph, node, visited, my_stack):
return True
return False
def detect_cycle_recursive(graph, node, visited, my_stack):
if my_stack[node]:
return True
if visited[node]:
return False
visited[node] = True
my_stack[node] = True
for adjacent in graph.graph[node]:
if detect_cycle_recursive(graph, adjacent, visited, my_stack):
return True
my_stack[node] = False
return False
if __name__ == "__main__":
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 1)
g.add_edge(3, 0)
print("Does the graph contain a cycle?", detect_cycle(g))
When we run this code with the given graph, it will detect the presence of a cycle and return True. This is because there is a cycle in the graph: 0 → 1 → 2 → 1, which forms a cycle.
