DSA Cycle Detection — Directed & Undirected Visualized

Learn cycle detection — DFS three-color algorithm, Floyd tortoise & hare, topological sort guard, interactive visualizer, and dependency graph examples.

Jul 4, 20264 min read

Introduction

Cycle detection asks: does a path return to a previously visited node? Critical for dependency resolution, deadlock detection, and topological sorting.

A directed graph with a cycle is not a DAG — npm, webpack, and build tools must detect cycles before ordering tasks.

Quick index

#	Section
1	Why cycles matter
2	Interactive visualizer
3	Full implementation
4	Algorithm comparison
5	Real-life examples

1. Why cycles matter

plaintext

Directed cycle:     A → B → C → D → A
 
DAG (no cycle):     A → B → C
                    ↓
                    D

With cycle	Without cycle (DAG)
Topological sort fails	Tasks can be ordered
Infinite loops in traversal	Guaranteed termination
Circular npm deps	Clean install order

Back to index

2. Interactive visualizer

Cycle Detection — DFS & Floyd

Detect cycles in directed graphs (DFS colors) and linked structures (Floyd tortoise & hare).

Directed acyclic graph — no path returns to a previously visited node.

DAG properties

// Task scheduling, build dependencies
// Topological sort only works on DAGs

hasCycle(dag)	→ false

npm install order requires a DAG — cycles mean circular deps.

Directed

DFS colors

Linked list

Floyd

Time

O(V+E)

Back to index

3. Full implementation

// Directed graph — DFS three-color
function hasCycleDirected(graph) {
  const WHITE = 0,
    GRAY = 1,
    BLACK = 2
  const color = {}
 
  function dfs(u) {
    color[u] = GRAY
    for (const v of graph[u] ?? []) {
      if (color[v] === GRAY) return true // back edge → cycle
      if (color[v] === WHITE && dfs(v)) return true
    }
    color[u] = BLACK
    return false
  }
 
  for (const node of Object.keys(graph)) {
    if (color[node] !== BLACK && dfs(node)) return true
  }
  return false
}
 
// Undirected graph — DFS with parent tracking
function hasCycleUndirected(graph) {
  const visited = new Set()
 
  function dfs(u, parent) {
    visited.add(u)
    for (const v of graph[u] ?? []) {
      if (!visited.has(v)) {
        if (dfs(v, u)) return true
      } else if (v !== parent) {
        return true
      }
    }
    return false
  }
 
  for (const node of Object.keys(graph)) {
    if (!visited.has(node) && dfs(node, null)) return true
  }
  return false
}
 
// Linked list — Floyd tortoise & hare
function hasCycleLinkedList(head) {
  let slow = head,
    fast = head
  while (fast?.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
}
 
function topologicalSort(graph) {
  if (hasCycleDirected(graph)) throw new Error('Cycle detected')
  const visited = new Set(),
    stack = []
 
  function dfs(u) {
    visited.add(u)
    for (const v of graph[u] ?? []) {
      if (!visited.has(v)) dfs(v)
    }
    stack.push(u)
  }
 
  for (const node of Object.keys(graph)) {
    if (!visited.has(node)) dfs(node)
  }
  return stack.reverse()
}

Function calls with output

// ── Demo calls — output shown on the right ──
const dag = { A: ['B', 'C'], B: ['D'], C: ['F'], D: [], E: [], F: [] }
const cycle = { A: ['B'], B: ['C'], C: ['D'], D: ['A'] }
 
hasCycleDirected(dag) // → false
hasCycleDirected(cycle) // → true
topologicalSort(dag) // → ['A', 'C', 'F', 'B', 'D'] (one valid order)
topologicalSort(cycle) // → Error: Cycle detected
 
hasCycleLinkedList(cyclicHead) // → true
hasCycleLinkedList(linearHead) // → false

Back to index

4. Algorithm comparison

Graph type	Algorithm	Time	Space
Directed	DFS three-color	O(V + E)	O(V)
Undirected	DFS + parent	O(V + E)	O(V)
Linked list	Floyd tortoise & hare	O(n)	O(1)
All nodes	Union-Find (undirected)	O(E × α(V))	O(V)

Back to index

5. Real-life examples

Scenario	Detection method
npm circular deps	DFS on package dependency graph
Deadlock (wait-for graph)	Cycle in resource allocation graph
Spreadsheet circular refs	DFS on cell formula graph
Linked list loop	Floyd tortoise & hare

npm circular dependency

Package A requires B, B requires C, C requires A — npm detects the cycle before install.

package-a → package-b

package-b → package-c

package-c → package-a

Directed edges = requires relationship.

Real-world implementation

function detectCircularDeps(packages) {
  const graph = {}
  for (const pkg of packages) {
    graph[pkg.name] = pkg.deps
  }
  return hasCycleDirected(graph)
}

// packages: A→B, B→C, C→A → cycle!

Full working code for the scenario above.

Function calls with output

// ── Function calls with output ──
const pkgs = [{ name:"a", deps:["b"] }, ...]

Side output shows return value after each call — step through to trace execution.

Back to index

Summary

Detect cycles before topological sort or dependency resolution. Directed graphs use DFS colors; linked lists use Floyd.

Next reads: Graph Traversal · DSA Graphs

Share this article

X LinkedIn Facebook

Subscribe to my newsletter

Stay up to date and get notified when I share new contents.

No spam ever, unsubscribe anytime

Back to Blog

DSA Graphs Cycle Detection Algorithms

DSA Cycle Detection — Directed & Undirected Visualized

Learn cycle detection — DFS three-color algorithm, Floyd tortoise & hare, topological sort guard, interactive visualizer, and dependency graph examples.

Jul 4, 20264 min read

Introduction

Cycle detection asks: does a path return to a previously visited node? Critical for dependency resolution, deadlock detection, and topological sorting.

A directed graph with a cycle is not a DAG — npm, webpack, and build tools must detect cycles before ordering tasks.

Quick index

#	Section
1	Why cycles matter
2	Interactive visualizer
3	Full implementation
4	Algorithm comparison
5	Real-life examples

1. Why cycles matter

plaintext

Directed cycle:     A → B → C → D → A
 
DAG (no cycle):     A → B → C
                    ↓
                    D

With cycle	Without cycle (DAG)
Topological sort fails	Tasks can be ordered
Infinite loops in traversal	Guaranteed termination
Circular npm deps	Clean install order

Back to index

2. Interactive visualizer

Cycle Detection — DFS & Floyd

Detect cycles in directed graphs (DFS colors) and linked structures (Floyd tortoise & hare).

Directed acyclic graph — no path returns to a previously visited node.

DAG properties

// Task scheduling, build dependencies
// Topological sort only works on DAGs

hasCycle(dag)	→ false

npm install order requires a DAG — cycles mean circular deps.

Directed

DFS colors

Linked list

Floyd

Time

O(V+E)

Back to index

3. Full implementation

// Directed graph — DFS three-color
function hasCycleDirected(graph) {
  const WHITE = 0,
    GRAY = 1,
    BLACK = 2
  const color = {}
 
  function dfs(u) {
    color[u] = GRAY
    for (const v of graph[u] ?? []) {
      if (color[v] === GRAY) return true // back edge → cycle
      if (color[v] === WHITE && dfs(v)) return true
    }
    color[u] = BLACK
    return false
  }
 
  for (const node of Object.keys(graph)) {
    if (color[node] !== BLACK && dfs(node)) return true
  }
  return false
}
 
// Undirected graph — DFS with parent tracking
function hasCycleUndirected(graph) {
  const visited = new Set()
 
  function dfs(u, parent) {
    visited.add(u)
    for (const v of graph[u] ?? []) {
      if (!visited.has(v)) {
        if (dfs(v, u)) return true
      } else if (v !== parent) {
        return true
      }
    }
    return false
  }
 
  for (const node of Object.keys(graph)) {
    if (!visited.has(node) && dfs(node, null)) return true
  }
  return false
}
 
// Linked list — Floyd tortoise & hare
function hasCycleLinkedList(head) {
  let slow = head,
    fast = head
  while (fast?.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
}
 
function topologicalSort(graph) {
  if (hasCycleDirected(graph)) throw new Error('Cycle detected')
  const visited = new Set(),
    stack = []
 
  function dfs(u) {
    visited.add(u)
    for (const v of graph[u] ?? []) {
      if (!visited.has(v)) dfs(v)
    }
    stack.push(u)
  }
 
  for (const node of Object.keys(graph)) {
    if (!visited.has(node)) dfs(node)
  }
  return stack.reverse()
}

Function calls with output

// ── Demo calls — output shown on the right ──
const dag = { A: ['B', 'C'], B: ['D'], C: ['F'], D: [], E: [], F: [] }
const cycle = { A: ['B'], B: ['C'], C: ['D'], D: ['A'] }
 
hasCycleDirected(dag) // → false
hasCycleDirected(cycle) // → true
topologicalSort(dag) // → ['A', 'C', 'F', 'B', 'D'] (one valid order)
topologicalSort(cycle) // → Error: Cycle detected
 
hasCycleLinkedList(cyclicHead) // → true
hasCycleLinkedList(linearHead) // → false

Back to index

4. Algorithm comparison

Graph type	Algorithm	Time	Space
Directed	DFS three-color	O(V + E)	O(V)
Undirected	DFS + parent	O(V + E)	O(V)
Linked list	Floyd tortoise & hare	O(n)	O(1)
All nodes	Union-Find (undirected)	O(E × α(V))	O(V)

Back to index

5. Real-life examples

Scenario	Detection method
npm circular deps	DFS on package dependency graph
Deadlock (wait-for graph)	Cycle in resource allocation graph
Spreadsheet circular refs	DFS on cell formula graph
Linked list loop	Floyd tortoise & hare

npm circular dependency

Package A requires B, B requires C, C requires A — npm detects the cycle before install.

package-a → package-b

package-b → package-c

package-c → package-a

Directed edges = requires relationship.

Real-world implementation

function detectCircularDeps(packages) {
  const graph = {}
  for (const pkg of packages) {
    graph[pkg.name] = pkg.deps
  }
  return hasCycleDirected(graph)
}

// packages: A→B, B→C, C→A → cycle!

Full working code for the scenario above.

Function calls with output

// ── Function calls with output ──
const pkgs = [{ name:"a", deps:["b"] }, ...]

Side output shows return value after each call — step through to trace execution.

Back to index

Summary

Detect cycles before topological sort or dependency resolution. Directed graphs use DFS colors; linked lists use Floyd.