Detect a Cycle in a Directed Graph Using DFS

graphHasCycle.py

# Constants
UNVISITED = 0
VISITED = 1
EXPLORED = 2

# Test Adjacency List Graph
# 0 -> 1 -> 2 -> 3
graph = [[1], 
         [2], 
         [3], 
         []]

def graphHasCycle(graph):
  """
  :type graph List[List[int]]
  :rtype: bool
  """
  # Initialize State
  state = [UNVISITED for i in range(len(graph))]
            
  # Start DFS from each unvisited node
  for node in range(len(graph)):
    if state[node] == UNVISITED:
      ret = subGraphHasCycle(graph,node,state)
      if ret:
        return True
        
  return False
        
        
def subGraphHasCycle(graph, node, state):
        
  if state[node] == VISITED:
    return True
  if state[node] == EXPLORED:
    return False
        
  state[node] = VISITED
        
  for neighbor in graph[node]:
    ret = subGraphHasCycle(graph, neighbor, state)
    if ret:
      return True
            
  state[node] = EXPLORED
  return False

print (graphHasCycle(graph))