How to detect a cycle in a Directed Graph?

Use DFS with a "recursion stack" flag. If you encounter a node already in the current recursion stack, a back-edge exists.

How to detect a cycle in an Undirected Graph?

During DFS, if you encounter a visited node that is NOT the parent of the current node, a cycle exists.

Why is Cycle Detection critical?

Cycles can cause infinite loops in algorithms and circular dependencies in systems that expect a hierarchy (DAG).

Cycle Detection

Learn how to detect cycles in graphs using Depth First Search (DFS). Essential for deadlock detection and validating dependencies.

Ready to start

Current

Recursion Stack

Cycle Found

Visited

Speed

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

Intuition

Imagine walking in a maze. If you keep following a path and end up at a spot you've already visited on your current journey, you've found a loop!

Cycle Detection finds these loops. The method differs slightly for directed vs. undirected graphs.

Concept

Directed Graph: A cycle exists if we revisit a node that is currently in the recursion stack (part of the current path).
Undirected Graph: A cycle exists if we visit a node that has already been visited, and it is NOT the parent of the current node.

How it Works

Directed Graph Algorithm:

Start DFS from an unvisited node.
Mark node as visited AND add to recursion stack.
For each neighbor:
- If in recursion stack -> Cycle found!
- If not visited -> Recursive DFS.
Remove from recursion stack when backtracking.

Undirected Graph Algorithm:

Start DFS, keeping track of the parent node.
Mark node as visited.
For each neighbor:
- If neighbor == parent -> Ignore (it's the edge we came from).
- If visited -> Cycle found!
- If not visited -> Recursive DFS.

Step-by-Step Breakdown

Watch the visualization:

Orange Node: Currently being visited.
Light Orange: In recursion stack (current path).
Red Node/Edge: The cycle that was detected.
Emerald Node: Visited and safe (no cycle found in this path).

When to Use

Use Cycle Detection when:

Checking for deadlocks in resource allocation systems.
Validating dependencies (e.g., circular dependencies in packages).
Verifying if a structure is a Tree (Trees have no cycles).
Infinite recurrence checks.

When NOT to Use

Shortest Path: It detects existence of a cycle, not path lengths.

How to Identify

Problems asking for "deadlock", "circular dependency", "infinite loop", or "valid tree" typically require cycle detection.

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep