Identifying Cycles in Directed Graphs with Tarjans Algorithm

In complex software architecture—ranging from package managers resolving module dependencies to compiler dead-code elimination and bundler graph optimizations—analyzing directed graphs for cycles is a foundational problem. When packages or components reference each other mutually, naive topological sorting algorithms fail or deadlock. To reliably analyze cycles, isolate circular dependencies, and condense cyclic subgraphs into directed acyclic meta-graphs, developers rely on identifying Strongly Connected Components (SCCs): maximal subgraphs where every vertex is reachable from every other vertex within that subgraph.

Published by Robert Tarjan in 1972, Tarjan's Strongly Connected Components algorithm partitions an entire directed graph in a single Depth-First Search (DFS) traversal running in linear O(V + E) time. As the DFS explores each unvisited vertex, it assigns a monotonically increasing discovery index and tracks a "low-link" value representing the smallest discovery index reachable through the current subtree, including back-edges to nodes currently stored on an auxiliary tracking stack. When the search backtracks to a root node whose discovery index equals its low-link value, the algorithm pops the entire component off the stack in one operation, isolating cyclic clusters with mathematical precision and zero redundant graph traversals.

Example #

// Directed graph with circular dependencies represented as an adjacency list
const dependencyGraph = {
  // Cycle 1: auth -> session -> token -> auth
  auth: ['session', 'logger'],
  session: ['token'],
  token: ['auth'],
  // Independent leaf nodes
  logger: ['format'],
  format: [],
  // Cycle 2: api -> router -> api
  api: ['router'],
  router: ['api', 'logger']
};

Implementation #

/**
 * Tarjan's Strongly Connected Components algorithm for directed graphs.
 * Runs in O(V + E) time and O(V) space.
 *
 * @param {Record<string, string[]>} graph - Adjacency list representation
 * @returns {string[][]} Array of strongly connected components
 */
function findStronglyConnectedComponents(graph) {
  let index = 0;
  const indices = new Map();
  const lowLink = new Map();
  const onStack = new Set();
  const stack = [];
  const sccs = [];

  function strongConnect(node) {
    // 1. Assign discovery index and initialize low-link value
    indices.set(node, index);
    lowLink.set(node, index);
    index++;

    stack.push(node);
    onStack.add(node);

    // 2. Explore directed edges to neighbor vertices
    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!indices.has(neighbor)) {
        // Successor has not been visited; recurse down DFS tree
        strongConnect(neighbor);
        lowLink.set(node, Math.min(lowLink.get(node), lowLink.get(neighbor)));
      } else if (onStack.has(neighbor)) {
        // Successor is on the stack and hence in the current DFS path (back-edge)
        lowLink.set(node, Math.min(lowLink.get(node), indices.get(neighbor)));
      }
    }

    // 3. If node is a root of an SCC, pop the component from the stack
    if (lowLink.get(node) === indices.get(node)) {
      const component = [];
      let w;
      do {
        w = stack.pop();
        onStack.delete(w);
        component.push(w);
      } while (w !== node);

      sccs.push(component);
    }
  }

  // Iterate through all nodes to ensure disconnected components are visited
  for (const node of Object.keys(graph)) {
    if (!indices.has(node)) {
      strongConnect(node);
    }
  }

  return sccs;
}

// Identify circular subgraphs (components with > 1 node or self-loops)
const components = findStronglyConnectedComponents(dependencyGraph);
const cycles = components.filter((comp) => comp.length > 1);

console.log('All SCCs:', components);
// Output includes: [['format'], ['logger'], ['token', 'session', 'auth'], ['router', 'api']]
console.log('Circular Dependency Cycles:', cycles);
// Output: [['token', 'session', 'auth'], ['router', 'api']]

Main Point: Tarjan's algorithm isolates circular dependency groups and partitions directed graphs into strongly connected components in a single linear O(V + E) depth-first traversal.

Credits #

Photo by Hunters Race on Unsplash

← Home