Skip to main content

Cycle Detection

Does a path exist that starts and ends at the same vertex without retracing an edge? The answer splits on direction: an undirected graph only needs a visited set plus the parent you arrived from, while a directed graph needs to distinguish "still on my current path" from "already finished," which takes a third state.

The full derivation - the WHITE/GRAY/BLACK colouring, why a back edge is a cycle, why parent-skip is required in undirected and a bug in directed, and the BFS forms of both - lives on Cycles & Ordering.

Undirected​

Undirected Graph Cycle​

Medium·
2 Approaches
FIG. UNDIRECTED GRAPH CYCLE● INTERACTIVE
visualization loads as you reach it
from collections import defaultdict
 
 
class Solution:
def isCycle(self, V, edges):
graph = defaultdict(list)
for src, dst in edges:
graph[src].append(dst)
graph[dst].append(src)
 
visited = set()
 
for node in range(V):
if node not in visited:
if self.dfs_cycle_detection(graph, visited, node, -1):
return True
 
return False
 
def dfs_cycle_detection(self, graph, visited, curNode, parentNode):
visited.add(curNode)
 
for neighbor in graph[curNode]:
if neighbor == parentNode:
continue
 
if neighbor in visited:
return True
 
if self.dfs_cycle_detection(graph, visited, neighbor, curNode):
return True
 
return False

Directed​

Directed Graph Cycle​

2 Approaches
FIG. DIRECTED GRAPH CYCLE● INTERACTIVE
visualization loads as you reach it
from collections import defaultdict
 
 
class Solution:
def isCycle(self, V, edges):
graph = defaultdict(list)
for src, dst in edges:
graph[src].append(dst)
 
visited = set()
for node in range(V):
if node not in visited and self.dfs_cycle_detection(graph, node, visited, set()):
return True
 
return False
 
def dfs_cycle_detection(self, graph, curNode, visited, curPath):
if curNode in curPath:
return True
 
if curNode in visited:
return False
 
visited.add(curNode)
curPath.add(curNode)
 
for neighbor in graph[curNode]:
if self.dfs_cycle_detection(graph, neighbor, visited, curPath):
return True
 
curPath.remove(curNode)
return False