9.13 Cycle Detection

Problem

You need to determine whether a graph contains a cycle.

Many graph algorithms assume certain structural properties. A build system expects dependency graphs to be acyclic. A workflow engine expects tasks to form a valid execution order. A routing system may need to identify loops. A compiler may need to reject circular imports.

Before applying higher-level algorithms, it is often necessary to answer a simple question:

Does this graph contain a cycle?

The answer frequently determines whether a problem has a valid solution at all.

Solution

Use graph traversal to detect whether a path can return to a previously visited vertex.

The exact technique depends on whether the graph is directed or undirected.

For directed graphs, track traversal state.

For undirected graphs, track parent relationships.

These approaches reflect the different meanings of cycles in the two graph models.

Discussion

A cycle is a path that begins and ends at the same vertex.

Example:

A → B → C → A

or:

A — B — C — A

Cycles are not inherently good or bad.

Their significance depends on the application.

Examples where cycles are expected:

• Road networks
• Communication networks
• Social networks
• State machines

Examples where cycles are often invalid:

• Build dependencies
• Package dependencies
• Task scheduling
• Course prerequisites

Cycle detection therefore appears in both validation and analysis workflows.

Directed Cycles

Consider:

A → B
B → C
C → A

Starting at A:

A
↓
B
↓
C
↓
A

The traversal returns to a vertex already on the current path.

This is the defining characteristic of a directed cycle.

The challenge is distinguishing:

already visited

from:

currently being explored

Those are different situations.

DFS State Tracking

The standard solution uses three states.

UNVISITED
VISITING
VISITED

Meaning:

State	Meaning
UNVISITED	Vertex has never been seen
VISITING	Vertex is currently on the DFS path
VISITED	Exploration is complete

Encountering a VISITING vertex indicates a cycle.

Example:

A
↓
B
↓
C
↓
A

When DFS reaches the final A, it discovers a vertex already on the recursion path.

A cycle exists.

Recipe: Directed Cycle Detection

def has_cycle(graph):
    state = {}

    def dfs(vertex):
        if state.get(vertex) == "VISITING":
            return True

        if state.get(vertex) == "VISITED":
            return False

        state[vertex] = "VISITING"

        for neighbor in graph[vertex]:
            if dfs(neighbor):
                return True

        state[vertex] = "VISITED"

        return False

    for vertex in graph:
        if dfs(vertex):
            return True

    return False

Example:

graph = {
    "A": ["B"],
    "B": ["C"],
    "C": ["A"],
}

Result:

True

The graph contains a cycle.

Why the Three-State Method Works

Consider:

A → B → C

DFS begins:

VISITING(A)
VISITING(B)
VISITING(C)

Eventually:

VISITED(C)
VISITED(B)
VISITED(A)

No cycle exists.

Now consider:

A → B → C → A

When DFS reaches the final A:

A is VISITING

The traversal has discovered a back edge into the current recursion chain.

This can occur only if a cycle exists.

That observation forms the correctness argument.

Self-Loops

A self-loop is a cycle.

Example:

A → A

The algorithm detects it automatically.

graph = {
    "A": ["A"]
}

Execution:

VISITING(A)

neighbor = A

A already VISITING

Cycle detected.

No special handling is required.

Undirected Cycles

Undirected graphs require a different approach.

Consider:

A — B

The adjacency list contains:

{
    "A": ["B"],
    "B": ["A"]
}

Starting DFS from A:

A
↓
B

The traversal immediately sees:

B → A

but this does not indicate a cycle.

It is simply the edge used to arrive at B.

The algorithm must distinguish:

parent edge

from:

genuine cycle edge

Parent Tracking

The solution is to remember where each DFS call came from.

When exploring:

A → B

the edge:

B → A

is ignored because A is the parent.

Any other previously visited vertex indicates a cycle.

Recipe: Undirected Cycle Detection

def has_cycle(graph):
    visited = set()

    def dfs(vertex, parent):
        visited.add(vertex)

        for neighbor in graph[vertex]:
            if neighbor == parent:
                continue

            if neighbor in visited:
                return True

            if dfs(neighbor, vertex):
                return True

        return False

    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex, None):
                return True

    return False

Example:

graph = {
    "A": ["B", "C"],
    "B": ["A", "C"],
    "C": ["A", "B"],
}

Result:

True

The graph contains a cycle.

Understanding Back Edges

In DFS terminology, a back edge points to an ancestor in the DFS tree.

Consider:

A
↓
B
↓
C
↘
 A

The edge:

C → A

points upward in the DFS tree.

This is called a back edge.

A directed graph contains a cycle if and only if DFS discovers a back edge.

This characterization appears repeatedly in advanced graph algorithms.

Recipe: Find One Cycle

Sometimes existence is insufficient.

You need the actual cycle.

Store parent pointers during DFS.

def find_cycle(graph):
    state = {}
    parent = {}

    def dfs(vertex):
        state[vertex] = "VISITING"

        for neighbor in graph[vertex]:
            if state.get(neighbor) == "VISITING":
                cycle = [neighbor]

                current = vertex

                while current != neighbor:
                    cycle.append(current)
                    current = parent[current]

                cycle.append(neighbor)

                cycle.reverse()

                return cycle

            if state.get(neighbor) is None:
                parent[neighbor] = vertex

                result = dfs(neighbor)

                if result:
                    return result

        state[vertex] = "VISITED"

        return None

    for vertex in graph:
        if state.get(vertex) is None:
            result = dfs(vertex)

            if result:
                return result

    return None

Possible output:

[
    "A",
    "B",
    "C",
    "A"
]

This is useful when reporting dependency errors.

Kahn's Algorithm as Cycle Detection

Topological sorting provides another cycle-detection method.

Recall:

DAG

implies:

topological ordering exists

and:

cycle

implies:

topological ordering does not exist

Therefore:

order = topological_sort(graph)

if len(order) != len(graph):
    print("cycle detected")

This is often the preferred technique when dependency validation and ordering are both required.

Union-Find Cycle Detection

For undirected graphs, Union-Find provides another solution.

Process edges one by one.

for u, v in edges:

If:

find(u) == find(v)

then u and v already belong to the same connected component.

Adding the edge creates a cycle.

Otherwise:

union(u, v)

This approach is widely used in:

• Kruskal's algorithm
• Dynamic connectivity
• Network analysis

The full Union-Find data structure is covered in Chapter 11.

Applications

Cycle detection appears in many domains.

Build Systems

Parser
↓
Lexer
↓
Parser

Invalid.

Package Managers

A depends on B
B depends on A

Invalid.

Course Planning

Course A requires B
Course B requires A

Impossible.

Workflow Engines

Validate
↓
Process
↓
Validate

Infinite loop.

Routing Systems

Cycles may indicate routing loops.

Detection helps diagnose network problems.

Complexity Analysis

Let:

• V = number of vertices
• E = number of edges

DFS-based cycle detection:

Operation	Complexity
Directed cycle detection	O(V + E)
Undirected cycle detection	O(V + E)
Memory usage	O(V)

Each vertex is processed once.

Each edge is examined a constant number of times.

The algorithm is linear in graph size.

Common Pitfalls

Do not use undirected cycle-detection logic on directed graphs.

The parent rule is insufficient.

Do not confuse previously visited vertices with vertices on the current recursion path.

Only the latter indicates a directed cycle.

Do not forget disconnected components.

A cycle may exist in a region unreachable from the chosen start vertex.

Do not ignore self-loops.

A self-loop is a cycle.

Do not assume topological sorting always succeeds.

Failure often means a cycle exists.

Recipe: Validate a Dependency Graph

A common production workflow is:

if has_cycle(graph):
    raise ValueError(
        "Circular dependency detected"
    )

Only after validation succeeds should scheduling proceed.

order = topological_sort(graph)

Many build systems, workflow engines, package managers, and orchestration platforms follow exactly this pattern.

Takeaway

Cycle detection determines whether a graph contains paths that return to their starting point. In directed graphs, DFS identifies cycles through back edges and recursion-path tracking. In undirected graphs, parent tracking distinguishes genuine cycles from ordinary traversal edges. The algorithm runs in linear time, forms the basis of dependency validation and graph verification, and serves as a prerequisite for topological sorting, scheduling, workflow execution, and many advanced graph algorithms.