Cycle Detection

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.

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.

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.

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.