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

> Discover how the topological sort in javascript-algorithms handles directed graphs, noting its cycle detection limitations and how it avoids infinite recursion.

- Repository: [Oleksii Trekhleb/javascript-algorithms](https://github.com/trekhleb/javascript-algorithms)
- Tags: deep-dive
- Published: 2026-02-24

---

**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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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:

```javascript
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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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:

```javascript
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:

```javascript
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:

```javascript
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.