Cycle Detection in Graphs

In the previous lesson, we learned how Depth-First Search (DFS) dives deep into a graph before backtracking.

Now we will use DFS concepts to solve a very important real-world problem — detecting cycles in a graph.

Cycle detection plays a crucial role in deadlock detection, dependency resolution, and validation of system workflows.

What Is a Cycle?

A cycle exists in a graph when you can start at a node, follow a sequence of edges, and return to the same node again.

In simple terms, a cycle means:

You are stuck in a loop.

Cycles may be harmless in some graphs, but dangerous in others.

Why Cycle Detection Matters

Many real systems break if cycles are not handled properly.

For example:

• Task scheduling systems
• Course prerequisite systems
• Build and dependency managers

If a task depends on itself indirectly, the system can never proceed.

Types of Graphs and Cycles

Cycle detection depends on the type of graph.

There are two main cases:

• Undirected graphs
• Directed graphs

We will start with the simpler case — undirected graphs.

Cycle Detection in Undirected Graphs

In undirected graphs, a cycle exists if DFS encounters an already visited node that is not the parent.

The parent check is critical. Without it, every edge would look like a cycle.

DFS-Based Cycle Detection (Undirected)

graph = {
    'A': ['B'],
    'B': ['A', 'C', 'D'],
    'C': ['B'],
    'D': ['B', 'E'],
    'E': ['D']
}

visited = set()

def has_cycle(graph, node, parent):
    visited.add(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            if has_cycle(graph, neighbor, node):
                return True
        elif neighbor != parent:
            return True

    return False

print(has_cycle(graph, 'A', None))

This function explores the graph deeply and checks whether a back-edge exists.

How This Logic Works

When DFS reaches a visited node:

• If it is the parent → ignore
• If it is not the parent → cycle detected

This distinction prevents false positives.

Cycle Detection in Directed Graphs

Directed graphs require a different approach.

Here, cycles occur when a node is revisited while it is still in the recursion stack.

To detect this, we maintain two sets:

• Visited nodes
• Recursion stack

DFS-Based Cycle Detection (Directed)

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

visited = set()
rec_stack = set()

def has_cycle_directed(graph, node):
    visited.add(node)
    rec_stack.add(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            if has_cycle_directed(graph, neighbor):
                return True
        elif neighbor in rec_stack:
            return True

    rec_stack.remove(node)
    return False

print(has_cycle_directed(graph, 'A'))

If a node appears again in the recursion stack, a cycle is confirmed.

Real-World Example

Imagine a course system:

• Course A requires B
• Course B requires C
• Course C requires A

This loop makes it impossible to complete any course.

Cycle detection prevents such logical failures.

Time Complexity

Cycle detection using DFS runs in:

O(V + E)

Because each node and edge is visited once.

Mini Practice

Think about software packages.

What happens if two packages depend on each other?

That dependency loop is a cycle.

Exercises

Quick Quiz

In the next lesson, we will build on cycle detection to learn Topological Sorting, a powerful technique used in scheduling systems.