Cycle detection asks whether a graph contains a path that returns to a previously visited vertex in a way that forms a loop.
Cycles matter because they change which algorithms are valid.
Core Idea
In an undirected graph, DFS must avoid treating the edge back to the parent as a cycle. In a directed graph, DFS often tracks nodes currently in the recursion stack to find back edges.
The exact method depends on whether the graph is directed or undirected.
Function Contracts
has_directed_cycle(graph) expects a directed adjacency list and returns whether a directed cycle exists.
has_undirected_cycle(graph) expects an undirected adjacency list where each edge appears in both directions. It returns whether an undirected cycle exists, ignoring the ordinary edge back to the parent.
Python Example
def has_directed_cycle(graph):
visiting = set()
done = set()
def dfs(node):
if node in visiting:
return True
if node in done:
return False
visiting.add(node)
for neighbor in graph[node]:
if dfs(neighbor):
return True
visiting.remove(node)
done.add(node)
return False
return any(dfs(node) for node in graph)visiting tracks the current recursion path.
Directed Graph Meaning
In a directed graph, a cycle exists when DFS reaches a node already in the current recursion path. That means the path can return to an earlier active node.
The done set is different. Reaching a done node means that node was fully checked before, and no cycle was found through it.
Undirected Graph Version
In an undirected graph, every edge appears in both directions. The edge back to the parent is normal and should not be counted as a cycle:
def has_undirected_cycle(graph):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor == parent:
continue
if neighbor in visited:
return True
if dfs(neighbor, node):
return True
return False
return any(dfs(node, None) for node in graph if node not in visited)Complexity
Cycle detection with DFS is usually O(V + E) with an adjacency list.
Failure Example
Using only one visited set for directed cycle detection can confuse a finished node with a node currently in the recursion path. Reaching a finished node is harmless; reaching an active node means the path has looped back on itself.
That is why the directed version separates visiting from done.
Common Confusions
A repeated visit is not always a cycle. In directed cycle detection, reaching a node already marked done does not create a cycle.
Undirected and directed cycle detection use different details, even though both can use DFS.
Another common mistake is using only one visited set for directed cycle detection. A directed graph needs to know whether a node is currently active or already finished.
When To Use It
Use cycle detection for dependency validation, course scheduling, build ordering, graph consistency checks, and problems where loops make a process impossible or ambiguous.
If a directed dependency graph has a cycle, no valid topological order exists.
The Main Point
Cycle detection depends on graph direction. Directed graphs need active recursion-state tracking; undirected graphs need parent-edge handling.