Faangprep Logo
Log inStart free
Browse curriculum

Cycle Detection

Cycle detection finds whether a graph contains a cycle, using depth-first search (DFS). It is essential for deadlock detection and validating dependencies.

NEW ROOT

Still open (recursion stack)

Empty

Closed

Nothing closed yet

 

A has not been reached yet. Start a new DFS from it.

Next

Open A. It stays on the recursion stack until every edge out of it has been followed.

Edges

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:
  1. Start DFS from an unvisited node.
  2. Mark node as visited AND add to recursion stack.
  3. For each neighbor:
    • If in recursion stack -> Cycle found!
    • If not visited -> Recursive DFS.
  4. Remove from recursion stack when backtracking.
Undirected Graph Algorithm:
  1. Start DFS, keeping track of the parent node.
  2. Mark node as visited.
  3. 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:

  • Solid blue node: Currently being visited.
  • Pale blue node with a blue outline: Still open: on the recursion stack (the current path).
  • Green node: Closed: fully explored, no cycle found through it.
  • Red node/edge: The cycle that was detected.

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.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Topological Sort

Next

Connected Components

Frequently Asked Questions

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).