Cycle Detection determines whether a graph contains a path that eventually returns to a vertex already on the active path.

Cycles are sometimes valid and sometimes dangerous. In dependency graphs, build systems, workflows, prerequisite graphs, and DAGs, a cycle can make ordering impossible.

What is a cycle?

In:

A → B → C → D

there is no cycle.

If we add:

D → B

then:

B → C → D → B

forms a cycle.

Directed vs undirected graphs

Cycle detection differs significantly between directed and undirected graphs.

In directed graphs, direction matters and a previously visited vertex does not automatically mean a cycle.

In undirected graphs, returning to the parent through the same edge is also not a cycle.

Directed graphs: three-state DFS

A standard state model is:

0 = unvisited
1 = visiting
2 = finished

An edge to a visiting vertex is a back edge and proves a cycle.

function hasCycleDirected(graph) {
  const state = new Map();

  function dfs(node) {
    const currentState = state.get(node) ?? 0;

    if (currentState === 1) return true;
    if (currentState === 2) return false;

    state.set(node, 1);

    for (const next of graph[node] ?? []) {
      if (dfs(next)) return true;
    }

    state.set(node, 2);

    return false;
  }

  for (const node of Object.keys(graph)) {
    if ((state.get(node) ?? 0) === 0) {
      if (dfs(node)) return true;
    }
  }

  return false;
}

Why visited alone is insufficient

A vertex may already be fully processed by another DFS branch without forming a cycle.

The important distinction is:

visiting → currently active in recursion
finished → already completed

Only an edge to a currently active ancestor proves a directed cycle.

Recursion-stack version

The same idea can be represented with:

visited
active

sets.

Undirected graphs: DFS with parent

In an undirected graph, if we traverse:

A -- B

then from B we naturally see A again.

That is not a cycle; A is simply the parent.

A cycle exists when a visited neighbor is not the parent.

function hasCycleUndirected(graph) {
  const visited = new Set();

  function dfs(node, parent) {
    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        if (dfs(next, node)) {
          return true;
        }
      } else if (next !== parent) {
        return true;
      }
    }

    return false;
  }

  for (const node of Object.keys(graph)) {
    if (!visited.has(node)) {
      if (dfs(node, null)) return true;
    }
  }

  return false;
}

BFS for undirected cycle detection

BFS can also track (node, parent) pairs and detect a visited non-parent neighbor.

Union-Find for undirected graphs

Disjoint Set Union is useful when edges are processed one by one.

Before adding edge (u, v), if both endpoints already belong to the same set, the new edge creates a cycle.

This is especially useful in edge-stream or Kruskal-style workflows.

Kahn's algorithm for directed graphs

A directed graph is acyclic if all vertices can be removed by repeatedly processing vertices with in-degree zero.

If Kahn's topological-sort process handles fewer than V vertices, a cycle exists.

function hasCycleKahn(graph) {
  const nodes = new Set();

  for (const [u, neighbors] of Object.entries(graph)) {
    nodes.add(u);

    for (const v of neighbors) {
      nodes.add(v);
    }
  }

  const indegree = new Map();

  for (const node of nodes) {
    indegree.set(node, 0);
  }

  for (const neighbors of Object.values(graph)) {
    for (const v of neighbors) {
      indegree.set(v, indegree.get(v) + 1);
    }
  }

  const queue = [];

  for (const node of nodes) {
    if (indegree.get(node) === 0) {
      queue.push(node);
    }
  }

  let head = 0;
  let processed = 0;

  while (head < queue.length) {
    const node = queue[head++];
    processed++;

    for (const next of graph[node] ?? []) {
      indegree.set(next, indegree.get(next) - 1);

      if (indegree.get(next) === 0) {
        queue.push(next);
      }
    }
  }

  return processed !== nodes.size;
}

Finding the actual cycle

Production tools often need more than a boolean result.

A build system may need to report:

A → B → C → A

Tracking parent links during DFS allows the cycle to be reconstructed when a back edge is found.

Self-loops and multigraphs

A self-loop:

A → A

is a cycle.

In undirected multigraphs, parallel edges may also form short cycles, so edge IDs may be needed rather than simple parent-vertex checks.

Disconnected graphs

A cycle may exist in any connected component.

Therefore cycle detection must start a new traversal from every unvisited vertex.

Real-world applications

Circular module dependencies

Auth → User → Email → Auth

can make initialization or build ordering impossible.

Package dependencies

Package managers can use cycle detection to validate dependency graphs.

Workflow engines

A workflow such as:

Draft → Review → Approve → Draft

may become an unintended infinite loop.

Course prerequisites

A cyclic prerequisite graph has no valid starting course.

Build systems

Cycle detection determines whether a dependency graph can be topologically ordered.

Spreadsheet circular references

Formula dependencies such as:

A1 → B1 → C1 → A1

form a cycle.

Service dependency analysis

Cycles between microservices can reveal tight coupling and failure-propagation risks.

DAG validation

A Directed Acyclic Graph (DAG) is simply a directed graph with no cycle.

Both three-state DFS and Kahn's algorithm are standard DAG validation techniques.

Relationship with topological sorting

A directed graph has a valid topological ordering if and only if it is acyclic.

Therefore:

cycle exists
→ no valid topological order

Floyd's cycle detection

Floyd's tortoise-and-hare algorithm is different from general graph cycle detection.

It is suited to structures where every state has a single next pointer, such as linked lists or functional graphs.

function hasCycleLinkedList(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
}

Complexity

DFS-based detection:

Time:  O(V + E)
Space: O(V)

Kahn's algorithm:

Time:  O(V + E)
Space: O(V)

Union-Find across edges is nearly linear:

O(E α(V))

Choosing the method

| Graph / structure | Common method | |---|---| | Directed graph | Three-state DFS | | Directed graph | Recursion stack | | DAG validation | Kahn / DFS | | Undirected graph | DFS + parent | | Undirected edge stream | Union-Find | | Linked list / functional graph | Floyd |

Common mistakes

• using only visited for directed graphs,
• forgetting parent tracking in undirected graphs,
• checking only one component,
• using Union-Find for directed cycle semantics,
• ignoring recursion depth,
• failing to report the actual cycle when diagnostics matter,
• mishandling multigraph parallel edges.

TypeScript

type Graph = Record<string, string[]>;

function hasCycleDirected(
  graph: Graph
): boolean {
  const state = new Map<string, number>();

  function dfs(node: string): boolean {
    const currentState = state.get(node) ?? 0;

    if (currentState === 1) return true;
    if (currentState === 2) return false;

    state.set(node, 1);

    for (const next of graph[node] ?? []) {
      if (dfs(next)) return true;
    }

    state.set(node, 2);

    return false;
  }

  for (const node of Object.keys(graph)) {
    if ((state.get(node) ?? 0) === 0) {
      if (dfs(node)) return true;
    }
  }

  return false;
}

Summary

Cycle detection is not one single algorithm.

The right method depends on the graph:

Directed
→ visiting / finished DFS
→ recursion stack
→ Kahn

Undirected
→ parent tracking
→ Union-Find

Linked list
→ Floyd

With adjacency lists, DFS and Kahn usually run in O(V + E) time.

The engineering value is substantial because cycle detection validates dependency graphs, workflows, build orders, DAGs, package graphs, and many other real systems.