Cycle Detection in Directed and Undirected Graphs
Detect cycles in undirected graphs with parent tracking and in directed graphs with DFS color-coding (white/grey/black three-state visited).
Cycle Detection in Directed and Undirected Graphs is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Why Cycle Detection Matters
A cycle in a graph is a path that starts and ends at the same node. Cycle detection is critical in many algorithms: topological sort fails on cyclic graphs, dependency resolution must detect circular dependencies, and deadlock detection in OS scheduling requires finding cycles in resource-allocation graphs. The approach differs between undirected and directed graphs — they require fundamentally different algorithms.
from collections import defaultdict
# Undirected cycle: A-B-C-A (triangle)
undirected = defaultdict(list)
for u, v in [('A','B'),('B','C'),('C','A')]:
undirected[u].append(v)
undirected[v].append(u)
# Directed cycle: A->B->C->A
directed = defaultdict(list)
for u, v in [('A','B'),('B','C'),('C','A')]:
directed[u].append(v) # one direction only
# Key difference:
# Undirected: edge A-B appears as both A->B and B->A
# Must track parent to distinguish cycle from back-edge to parent
print('Undirected and directed cycles need different detection')Undirected Cycle Detection with DFS
In an undirected graph, a cycle exists if DFS visits a node that is already in the current path (not just visited). The challenge: every edge appears in both directions, so when we visit a child node, its neighbour list includes our current node (the parent). We must track the parent of each node to avoid falsely flagging the edge back to the parent as a cycle. If we encounter a visited node that is not our parent, we've found a cycle.
def has_cycle_undirected(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
if dfs(nb, node): # recurse with current as parent
return True
elif nb != parent: # visited and not parent = CYCLE
return True
return False
for node in range(n):
if node not in visited:
if dfs(node, -1): # -1 = no parent for root
return True
return False
print(has_cycle_undirected(4, [(0,1),(1,2),(2,3),(3,1)])) # True
print(has_cycle_undirected(3, [(0,1),(1,2)])) # FalseUndirected Cycle with BFS
BFS cycle detection in an undirected graph also tracks the parent of each visited node. When processing a node's neighbours, if a neighbour is already visited and is not the current node's parent, a cycle exists. Use a dictionary to store parents. This O(V + E) approach avoids the recursion limit concern and is the preferred iterative alternative for large graphs.
from collections import deque, defaultdict
def has_cycle_bfs_undirected(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
for start in range(n):
if start in visited:
continue
visited.add(start)
parent = {start: -1}
queue = deque([start])
while queue:
node = queue.popleft()
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
parent[nb] = node
queue.append(nb)
elif parent[node] != nb: # visited and not parent = CYCLE
return True
return False
print(has_cycle_bfs_undirected(4, [(0,1),(1,2),(2,0)])) # TrueDirected Cycle: Why Parent Tracking Fails
In a directed graph, parent tracking is insufficient. Consider A→C and B→C: node C has two 'parents' but no cycle. The correct approach uses three-state coloring: white (unvisited), gray (in the current DFS path/stack), black (fully processed). A cycle exists if we ever encounter a gray node during DFS — meaning we've found a back edge to an ancestor in the current path.
# Three-state DFS coloring:
# WHITE (0): not yet visited
# GRAY (1): currently being visited (in DFS stack)
# BLACK (2): fully visited (all descendants processed)
# Why parent fails for directed graphs:
# A -> C (no cycle)
# B -> C (no cycle)
# If we DFS from A, mark C gray
# Then DFS from B finds C is gray -- but this is NOT a cycle!
# C is gray from A's path, not B's path.
# Parent tracking only works when the back-edge goes to the IMMEDIATE parent.
print('Directed graph: use 3-state coloring (white/gray/black)')Directed Cycle Detection with 3-State DFS
Use an array state[] with values 0 (white/unvisited), 1 (gray/in-stack), 2 (black/done). Start DFS, marking the node gray on entry and black on exit. If DFS ever reaches a gray node, a back edge is found — there is a cycle. If it reaches a black node, that path is already fully explored and cycle-free, so skip it.
def has_cycle_directed(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
state = [0] * n # 0=white, 1=gray, 2=black
def dfs(node):
state[node] = 1 # mark gray (in stack)
for nb in graph[node]:
if state[nb] == 1: # gray = back edge = CYCLE
return True
if state[nb] == 0: # white = unvisited
if dfs(nb):
return True
state[node] = 2 # mark black (fully processed)
return False
for node in range(n):
if state[node] == 0:
if dfs(node):
return True
return False
print(has_cycle_directed(4, [(0,1),(1,2),(2,0),(2,3)])) # True (0->1->2->0)
print(has_cycle_directed(3, [(0,1),(1,2)])) # FalseCourse Schedule: Cycle in a DAG
Course Schedule (LeetCode #207) asks if all courses can be finished given prerequisites. Model courses as nodes and prerequisites as directed edges. The courses can all be finished if and only if the graph is a DAG (no cycles). Use the 3-state DFS cycle detection — if a cycle is found, return False; otherwise return True.
from collections import defaultdict
def can_finish(num_courses, prerequisites):
graph = defaultdict(list)
for a, b in prerequisites:
graph[b].append(a) # b is prerequisite for a: b -> a
state = [0] * num_courses
def dfs(course):
if state[course] == 1: return False # cycle!
if state[course] == 2: return True # already verified
state[course] = 1 # mark as in-progress
for next_course in graph[course]:
if not dfs(next_course):
return False
state[course] = 2 # mark as done
return True
return all(dfs(i) for i in range(num_courses) if state[i] == 0)
print(can_finish(2, [[1,0]])) # True: take 0 then 1
print(can_finish(2, [[1,0],[0,1]])) # False: circular dependencyCycle Detection with Kahn's Algorithm (BFS)
An alternative cycle detection for directed graphs uses Kahn's BFS topological sort. Count in-degrees of all nodes. Put nodes with in-degree 0 in a queue. Process each: decrement neighbours' in-degrees, enqueue those that reach 0. If the count of processed nodes equals V, no cycle; otherwise a cycle exists (the unprocessed nodes form cycles). This O(V + E) approach is intuitive and easier to remember than 3-state DFS.
from collections import defaultdict, deque
def has_cycle_kahn(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
# Start with all zero in-degree nodes
queue = deque(i for i in range(n) if in_degree[i] == 0)
processed = 0
while queue:
node = queue.popleft()
processed += 1
for nb in graph[node]:
in_degree[nb] -= 1
if in_degree[nb] == 0:
queue.append(nb)
return processed != n # if not all processed, cycle exists
print(has_cycle_kahn(4, [(0,1),(1,2),(2,0),(2,3)])) # True
print(has_cycle_kahn(3, [(0,1),(1,2)])) # FalseFind the Cycle: Collecting Cycle Nodes
Sometimes you need to identify which nodes are part of a cycle, not just detect its existence. During 3-state DFS, when a back edge is found, trace back through the call stack (or a path stack) to collect all nodes between the ancestor and the current node. A path stack maintained alongside the state array captures the current DFS path, enabling O(cycle_length) cycle reconstruction.
def find_cycle_nodes(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
state = [0] * n
path = [] # current DFS path
cycle = []
def dfs(node):
state[node] = 1
path.append(node)
for nb in graph[node]:
if state[nb] == 1: # back edge -> found cycle
start = path.index(nb)
cycle.extend(path[start:])
return True
if state[nb] == 0 and dfs(nb):
return True
path.pop()
state[node] = 2
return False
for i in range(n):
if state[i] == 0 and dfs(i):
break
return cycle
print(find_cycle_nodes(4, [(0,1),(1,2),(2,0),(2,3)])) # [0, 1, 2]Find Eventual Safe States
Find Eventual Safe States (LeetCode #802) asks which nodes eventually lead to a terminal node (no outgoing edges) without getting stuck in a cycle. A node is 'safe' if all paths from it lead to terminal nodes. Use 3-state DFS: nodes that are black (fully processed without cycle detection) are safe. Nodes that are part of or lead to a cycle are not safe.
def eventual_safe_nodes(graph):
n = len(graph)
state = [0] * n # 0=unvisited, 1=visiting, 2=safe
def dfs(node):
if state[node] == 1: # currently visiting = cycle
return False
if state[node] == 2: # already verified safe
return True
state[node] = 1 # mark as visiting
for nb in graph[node]:
if not dfs(nb):
return False # leads to cycle, not safe
state[node] = 2 # mark as safe
return True
return [i for i in range(n) if dfs(i)]
# [[1,2],[2,3],[5],[0],[5],[],[]] means:
# 0->[1,2], 1->[2,3], 2->[5], 3->[0] (cycle!), 4->[5], 5->[], 6->[]
print(eventual_safe_nodes([[1,2],[2,3],[5],[0],[5],[],[]]))
# [2, 4, 5, 6]Redundant Connection in Undirected Graph
Redundant Connection (LeetCode #684) finds the edge that creates a cycle when added to an otherwise acyclic undirected graph. While this can be solved with DFS cycle detection, the cleanest solution uses Union-Find (DSU): process edges one by one; if both endpoints are already connected (same component), the current edge creates a cycle and is the answer. DSU gives O(alpha(n)) per operation — effectively O(1).
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # path compression
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # already connected = cycle!
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v] # this edge creates the cycle
return []
print(find_redundant_connection([[1,2],[1,3],[2,3]])) # [2,3]
print(find_redundant_connection([[1,2],[2,3],[3,4],[1,4],[1,5]])) # [1,4]Summary: Cycle Detection Strategies
To summarise the cycle detection toolkit: for undirected graphs, use DFS with parent tracking or Union-Find. For directed graphs, use 3-state DFS (white/gray/black) or Kahn's BFS topological sort. Choose Union-Find when you are adding edges one at a time (online). Choose Kahn's when you also need the topological order. Choose 3-state DFS when you need to identify the specific cycle nodes. Always state the distinction between directed and undirected when discussing cycle detection in interviews.
# Cycle detection summary:
# Graph type | Algorithm | Complexity
# ------------|----------------------|-----------
# Undirected | DFS + parent track | O(V + E)
# Undirected | Union-Find (DSU) | O(E * alpha(V))
# Directed | DFS 3-state (W/G/B) | O(V + E)
# Directed | Kahn's BFS topo sort | O(V + E)
# When to choose:
# Online (edges added one at a time): Union-Find
# Need topological order too: Kahn's BFS
# Need cycle nodes identified: 3-state DFS with path stack
# Simple existence check: any of the above
print('Always clarify directed vs undirected before coding')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: undirected cycle detection with parent-tracking DFS, directed cycle detection with 3-state white/gray/black coloring, Kahn's BFS alternative for directed graphs, and applications including course schedule, redundant connection, and eventual safe states. Next up we dive into dynamic programming foundations.
Frequently asked questions
Is the “Cycle Detection in Directed and Undirected Graphs” lesson free?
Yes — the full text of “Cycle Detection in Directed and Undirected Graphs” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Cycle Detection in Directed and Undirected Graphs”?
Detect cycles in undirected graphs with parent tracking and in directed graphs with DFS color-coding (white/grey/black three-state visited). You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Cycle Detection in Directed and Undirected Graphs” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Graph Representations and Traversal Setup
- BFS: Shortest Path and Level Traversal
- DFS: Connected Components and Flood Fill
- Cycle Detection in Directed and Undirected Graphs