How Does the Topological Sorting Algorithm Detect Cycles in Directed Graphs?

The topological sort implementation in trekhleb/javascript-algorithms does not detect cycles; it silently skips back-edges via a visitedSet guard to prevent infinite recursion, returning a complete vertex list even for cyclic graphs.

The JavaScript Algorithms repository provides a depth-first search based topological sorting utility at src/algorithms/graph/topological-sorting/topologicalSort.js. While this algorithm prevents infinite loops during traversal, it does not explicitly report when a directed graph contains a cycle. Understanding this limitation is critical for applications that require valid directed acyclic graph (DAG) guarantees.

How topologicalSort.js Handles Visited Vertices

The implementation relies on the generic depthFirstSearch utility and configures three callback hooks to manage traversal state.

Tracking State with unvisitedSet and visitedSet

The algorithm initializes two key data structures before traversal begins, as shown in lines 9-16 of topologicalSort.js:

• unvisitedSet: A dictionary containing all vertices initially, ensuring disconnected components are processed
• visitedSet: An empty object that tracks vertices currently in the active DFS recursion stack

The allowTraversal Callback Prevents Revisiting

The critical logic for cycle handling resides in the allowTraversal callback defined at lines 32-34:

allowTraversal: ({ nextVertex }) => {
  return !visitedSet[nextVertex.getKey()];
}

This guard returns false for any edge pointing to a vertex already present in visitedSet. When the DFS encounters a back-edge (indicating a cycle), it simply aborts traversal along that specific edge rather than throwing an error or returning a special value.

Building the Sorted Stack

The enterVertex callback adds the current vertex to visitedSet and removes it from unvisitedSet (lines 21-27), while leaveVertex pushes the vertex onto sortedStack (lines 28-31). The outer while loop (lines 37-44) continues until unvisitedSet is empty, guaranteeing every vertex is entered exactly once and added to the final result at line 47.

Why the Algorithm Does Not Detect Cycles

Unlike dedicated cycle detection routines, this topological sort implementation treats cycles as silent topological constraints to ignore rather than errors to report.

Silent Skipping of Back-Edges

When allowTraversal blocks a back-edge, the algorithm continues processing other neighbors. Because the vertex was already added to visitedSet during the initial entry, the recursion unwinds normally. The outer loop eventually processes all remaining vertices in unvisitedSet, including those participating in cycles, without distinguishing between acyclic and cyclic structures.

Returning a Complete Vertex List

The function returns sortedStack.toArray() regardless of whether any edges were skipped. For a cyclic graph, this produces a ordering that violates dependency constraints, but the function provides no indication that the input was invalid.

Explicit Cycle Detection in the Repository

For applications requiring cycle validation, the repository provides src/algorithms/graph/detect-cycle/detectDirectedCycle.js. This implementation uses the white-gray-black set algorithm to identify back-edges and reconstruct cycle paths.

The White-Gray-Black Approach

The detectDirectedCycle function maintains three sets to distinguish traversal states:

• White set: Vertices not yet visited
• Gray set: Vertices currently in the recursion stack (active DFS path)
• Black set: Vertices whose descendants have been fully processed

When DFS encounters a neighbor in the gray set, it has found a back-edge and can return the cycle mapping. This contrasts with topologicalSort, which uses a single visited set and cannot distinguish between cross-edges and back-edges.

Usage Pattern for Safe Sorting

Always verify acyclicity before sorting:

import detectDirectedCycle from 'src/algorithms/graph/detect-cycle/detectDirectedCycle';
import topologicalSort from 'src/algorithms/graph/topological-sorting/topologicalSort';

if (detectDirectedCycle(graph) !== null) {
  throw new Error('Graph contains a cycle – topological sort undefined');
}

const order = topologicalSort(graph);

Code Examples

Sorting a Valid DAG

This example demonstrates successful sorting on an acyclic graph:

import Graph from 'src/data-structures/graph/Graph';
import GraphVertex from 'src/data-structures/graph/GraphVertex';
import GraphEdge from 'src/data-structures/graph/GraphEdge';
import topologicalSort from 'src/algorithms/graph/topological-sorting/topologicalSort';

const graph = new Graph(true);
const a = new GraphVertex('A');
const b = new GraphVertex('B');
const c = new GraphVertex('C');

graph.addEdge(new GraphEdge(a, b)).addEdge(new GraphEdge(b, c));

const order = topologicalSort(graph);
console.log(order.map(v => v.getKey())); // ['A', 'B', 'C']

Detecting Cycles Before Sorting

This pattern prevents invalid sorts on cyclic inputs:

import Graph from 'src/data-structures/graph/Graph';
import GraphVertex from 'src/data-structures/graph/GraphVertex';
import GraphEdge from 'src/data-structures/graph/GraphEdge';
import detectDirectedCycle from 'src/algorithms/graph/detect-cycle/detectDirectedCycle';
import topologicalSort from 'src/algorithms/graph/topological-sorting/topologicalSort';

const graph = new Graph(true);
const a = new GraphVertex('A');
const b = new GraphVertex('B');
const c = new GraphVertex('C');

// Create cycle: A → B → C → A
graph.addEdge(new GraphEdge(a, b))
  .addEdge(new GraphEdge(b, c))
  .addEdge(new GraphEdge(c, a));

const cycle = detectDirectedCycle(graph);
if (cycle) {
  console.warn('Cycle detected:', cycle);
} else {
  const order = topologicalSort(graph);
  console.log(order.map(v => v.getKey()));
}

Summary

• The topologicalSort function in trekhleb/javascript-algorithms uses a visitedSet to prevent infinite recursion but does not explicitly detect or report cycles.
• The allowTraversal callback skips edges to already-visited vertices (lines 32-34), effectively ignoring back-edges rather than identifying them as cycles.
• The algorithm returns a complete vertex list for both acyclic and cyclic graphs, making external validation mandatory for reliable use.
• Use detectDirectedCycle with white-gray-black sets to explicitly check for cycles before invoking topological sort.

Frequently Asked Questions

Does the topological sort algorithm automatically detect cycles?

No. The implementation only prevents revisiting vertices during depth-first search to avoid infinite recursion. It silently skips back-edges and returns a result containing all vertices, providing no indication that the graph contains a cycle.

What happens if I run topologicalSort on a cyclic graph?

The function completes without error and returns an array of all vertices in some order. However, this ordering is not a valid topological sort because dependencies within the cycle are violated. You must validate the graph with detectDirectedCycle first.

How does detectDirectedCycle differ from the cycle handling in topologicalSort?

While topologicalSort uses a single visitedSet to block all revisits, detectDirectedCycle uses three sets (white, gray, black) to distinguish between fully processed vertices and those currently in the recursion stack. This allows it to identify specific back-edges and return the cycle path, whereas topologicalSort merely skips them.

Should I always check for cycles before running topologicalSort?

Yes. Since topologicalSort does not validate its input, always invoke detectDirectedCycle first when processing graphs of unknown structure. This ensures you only attempt to sort valid DAGs and can handle cyclic inputs gracefully with error messages or alternative logic.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}