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 Approachesclick to switch
FIG. UNDIRECTED GRAPH CYCLE● INTERACTIVE
visualization loads as you reach it
Time
O(V + E)
  • Building graph scans every edge twice (once per direction): O(E).
  • dfs_cycle_detection adds each node to visited once and, thanks to the if node not in visited guard in the outer loop, is only ever called from a fresh start once per node; each edge is examined from both endpoints across the whole run: O(V + E).
  • V is the number of vertices and E is the number of edges.
Space
O(V + E)
  • graph stores both directions of every edge, O(E).
  • visited holds up to V entries, and the recursion stack goes at most V deep: O(V).
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 Approachesclick to switch
FIG. DIRECTED GRAPH CYCLE● INTERACTIVE
visualization loads as you reach it
Time
O(V + 2E)
  • Building graph from edges is one O(E) pass over the edge list.
  • The DFS then visits each of the V nodes exactly once (the visited guard stops re-entry) and, across all recursive calls, follows each of the E edges once - an O(V + E) traversal.
  • The two O(E) contributions (the build pass and the traversal's edge-following) combine into a coefficient: O(V + 2E).
Space
O(3V + E)
  • graph stores V keys and E total neighbor entries across its adjacency lists - O(V + E).
  • visited holds up to V nodes once every node has been explored - O(V).
  • curPath (and the recursion call stack, whose depth matches curPath's size) holds up to V nodes along the deepest path - O(V).
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