Cycle Detection in Graphs Tutorial | Learn Data Structures

A cycle in a graph is a path that starts at a vertex, follows a sequence of edges, and eventually returns to the starting vertex. Detecting cycles is an important graph problem because cycles can affect dependency resolution, scheduling, network analysis, and many other algorithms.

The technique used to detect a cycle depends on whether the graph is undirected or directed. In an undirected graph, DFS can use a parent vertex to distinguish a normal connection back to the previous vertex from a real cycle. In a directed graph, DFS commonly uses vertex states or a recursion stack to detect a back edge.

What Is a Cycle?

Consider the following undirected graph:

0 ----- 1
|       |
|       |
2 ----- 3

Starting from vertex 0, we can travel through 1, 3, and 2 and eventually return to 0. This forms a cycle:

0 → 1 → 3 → 2 → 0

A graph can contain one cycle, several cycles, or no cycles at all.

Why Cycle Detection Matters

Cycles are not always errors. Some systems naturally contain cycles, such as road networks and social relationships. However, certain problems require a graph to be acyclic.

Detecting circular dependencies between software modules.
Validating dependency graphs before scheduling tasks.
Determining whether a directed dependency graph can be topologically sorted.
Detecting loops in network or relationship models.
Checking whether adding an edge creates a cycle.
Solving graph and interview problems involving connectivity.

Cycle Detection in an Undirected Graph

In an undirected graph, every edge can be traversed in both directions. This creates an important detail when using DFS.

Suppose DFS travels from vertex 0 to vertex 1. While processing vertex 1, the graph naturally contains an edge back to vertex 0. That edge alone does not indicate a cycle; it is simply the edge through which DFS arrived at vertex 1.

Therefore, cycle detection in an undirected graph keeps track of the parent of each vertex. If DFS encounters an already visited neighbor that is not the current vertex's parent, a cycle exists.

DFS Cycle Detection for an Undirected Graph

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

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

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

    return false;
  }

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

  return false;
}

const graph = {
  A: ["B", "C"],
  B: ["A", "C"],
  C: ["A", "B"]
};

console.log(hasCycle(graph)); // true

The outer loop is important because the graph may contain multiple disconnected components. Each unvisited component must be explored.

How the Parent Check Works

Consider an edge between A and B:

A ----- B

If DFS moves from A to B, then B sees A as an already visited neighbor. Because A is B's parent, this is not considered a cycle.

Now suppose B encounters another visited vertex C that is not its parent:

    A
   /   B---C

B or C can encounter an already visited vertex through a different edge. That indicates that the traversal has found an alternative path back into the explored portion of the graph, forming a cycle.

Undirected Graph: Example Without a Cycle

A ----- B ----- C
        |
        D

This graph is connected but does not contain a cycle. Every edge is part of a tree-like structure, so DFS never finds an already visited neighbor other than the parent.

Handling Disconnected Undirected Graphs

A graph may contain several disconnected components. Checking only one starting vertex is therefore insufficient.

const graph = {
  A: ["B"],
  B: ["A"],
  C: ["D"],
  D: ["C", "E"],
  E: ["D", "F"],
  F: ["E", "D"]
};

The algorithm must start DFS from every unvisited vertex. If any component contains a cycle, the graph contains a cycle.

Cycle Detection in a Directed Graph

Directed graphs require a different approach because the direction of an edge matters. The parent-based technique used for undirected graphs is not sufficient.

A common DFS technique uses three states:

State	Meaning
0	Vertex has not been visited.
1	Vertex is currently being explored.
2	Vertex and all of its outgoing paths have been processed.

If DFS encounters a neighbor whose state is 1, that neighbor is already part of the current recursion path. This indicates a directed cycle.

DFS Cycle Detection for a Directed Graph

function hasDirectedCycle(graph) {
  const state = {};

  for (const node of Object.keys(graph)) {
    state[node] = 0;
  }

  function dfs(node) {
    state[node] = 1;

    for (const neighbor of graph[node]) {
      if (state[neighbor] === 1) {
        return true;
      }

      if (state[neighbor] === 0 && dfs(neighbor)) {
        return true;
      }
    }

    state[node] = 2;
    return false;
  }

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

  return false;
}

const graph = {
  A: ["B"],
  B: ["C"],
  C: ["A"]
};

console.log(hasDirectedCycle(graph)); // true

The edge C → A points back to a vertex that is still being explored in the current DFS path. This is the condition that reveals the cycle.

Why a Simple Visited Set Is Not Enough for Directed Graphs

A directed graph can contain an edge to a vertex that has already been completely processed without containing a cycle.

A → B
A → C
B → C

When DFS reaches C through B, C may later be encountered from A. That does not mean there is a path from C back to A. A simple visited flag cannot distinguish this situation from a back edge. The three-state method separates vertices currently in the recursion path from vertices that have already been fully processed.

Recursion Stack Approach

The three-state method can also be expressed using two collections: visited and recursionStack.

function hasCycle(graph) {
  const visited = new Set();
  const recursionStack = new Set();

  function dfs(node) {
    visited.add(node);
    recursionStack.add(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor)) {
          return true;
        }
      } else if (recursionStack.has(neighbor)) {
        return true;
      }
    }

    recursionStack.delete(node);
    return false;
  }

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

  return false;
}

const graph = {
  A: ["B"],
  B: ["C"],
  C: ["A"]
};

console.log(hasCycle(graph)); // true

A vertex remains in the recursion stack while DFS is exploring paths originating from that vertex. Finding an edge to another vertex still in the stack indicates a back edge and therefore a cycle.

Cycle Detection Using BFS and Topological Sorting

A directed graph can also be checked for cycles using Kahn's algorithm, which repeatedly removes vertices with zero incoming edges.

If all vertices can be processed, the graph is acyclic. If some vertices remain unprocessed, those remaining dependencies contain a cycle.

function hasDirectedCycle(graph) {
  const indegree = {};
  const queue = [];

  for (const node of Object.keys(graph)) {
    indegree[node] = 0;
  }

  for (const node of Object.keys(graph)) {
    for (const neighbor of graph[node]) {
      indegree[neighbor]++;
    }
  }

  for (const node of Object.keys(indegree)) {
    if (indegree[node] === 0) {
      queue.push(node);
    }
  }

  let processed = 0;
  let index = 0;

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

    for (const neighbor of graph[node]) {
      indegree[neighbor]--;

      if (indegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  return processed !== Object.keys(graph).length;
}

const graph = {
  A: ["B"],
  B: ["C"],
  C: ["A"]
};

console.log(hasDirectedCycle(graph)); // true

This approach is especially useful when cycle detection is part of a dependency ordering or topological-sort problem.

Cycle Detection with Union-Find

For an undirected graph, the Disjoint Set Union (DSU), also called Union-Find, can detect whether adding an edge connects two vertices that are already in the same component.

If both endpoints already have the same representative, adding that edge creates a cycle. Otherwise, the two components can be merged.

class UnionFind {
  constructor(size) {
    this.parent = Array.from(
      { length: size },
      (_, index) => index
    );
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }

    return this.parent[x];
  }

  union(a, b) {
    const rootA = this.find(a);
    const rootB = this.find(b);

    if (rootA === rootB) {
      return false;
    }

    this.parent[rootB] = rootA;
    return true;
  }
}

function containsCycle(vertices, edges) {
  const uf = new UnionFind(vertices);

  for (const [a, b] of edges) {
    if (!uf.union(a, b)) {
      return true;
    }
  }

  return false;
}

const edges = [
  [0, 1],
  [1, 2],
  [2, 0]
];

console.log(containsCycle(3, edges)); // true

Union-Find is particularly useful when edges are processed incrementally and the problem naturally involves merging connected components.

DFS vs BFS vs Union-Find

Approach	Graph Type	Key Idea
DFS + Parent	Undirected	Visited neighbor that is not the parent indicates a cycle.
DFS + States	Directed	An edge to a currently visiting vertex indicates a cycle.
BFS / Kahn's Algorithm	Directed	Vertices left after zero-indegree processing indicate a cycle.
Union-Find	Undirected	An edge joining vertices already in the same set creates a cycle.

Time Complexity

For DFS or BFS on an adjacency-list representation, cycle detection typically visits each vertex and examines each edge once or a constant number of times.

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

Here, V is the number of vertices and E is the number of edges. The O(V) auxiliary space accounts for structures such as visited state, recursion stack, or a BFS queue.

Cycle Detection with an Adjacency Matrix

When a graph is represented by an adjacency matrix, discovering the neighbors of a vertex requires scanning its row. This can make traversal-based cycle detection O(V²) for a graph with V vertices.

const graph = [
  [0, 1, 1],
  [1, 0, 1],
  [1, 1, 0]
];

The matrix above represents three vertices where each vertex is connected to the other two, creating a cycle.

Real-World Example: Circular Dependencies

Software dependency systems provide a useful example of directed cycle detection. Suppose three modules depend on each other:

Module A → Module B
Module B → Module C
Module C → Module A

This dependency graph contains a cycle. A system attempting to resolve dependencies in a strict order cannot place all three modules in a valid topological ordering. Detecting the cycle allows the system to report or handle the circular dependency.

Cycle Detection and Topological Sorting

A directed graph has a topological ordering only when it is a Directed Acyclic Graph (DAG).

Consequently, cycle detection is often an important first step when working with task dependencies, build systems, course prerequisites, package dependencies, or other directed ordering problems.

Common Mistakes

Using the undirected parent technique directly on a directed graph.
Using only a visited set for directed DFS cycle detection.
Forgetting to check every disconnected component.
Marking a directed vertex as completely processed before its outgoing paths finish.
Forgetting that the edge back to a parent in an undirected graph is not itself a cycle.
Ignoring the graph representation when analyzing complexity.
Assuming every repeated vertex encountered during traversal automatically means a directed cycle.

A Simple Pattern to Remember

For an undirected graph, remember:

visited neighbor + neighbor is not parent
= cycle

For a directed graph, remember:

edge to a vertex currently in the DFS path
= cycle

These two patterns cover many common cycle-detection problems encountered in data structures and algorithm interviews.

Key Takeaways

A cycle is a path that eventually returns to a previously reached vertex in a way that forms a closed path.
Cycle detection depends on whether the graph is directed or undirected.
DFS with parent tracking is a common approach for undirected graphs.
DFS with three states or a recursion stack is commonly used for directed graphs.
Kahn's algorithm can detect cycles in directed graphs while performing topological processing.
Union-Find can detect cycles in undirected graphs as edges are added.
For adjacency-list DFS or BFS, typical time complexity is O(V + E).
Disconnected graphs require traversal from every unvisited vertex.
Cycle detection is useful in dependency resolution, scheduling, networks, and graph algorithms.

Topics

Cycle Detection in Graphs