Topological Sorting produces a linear ordering of the vertices of a directed graph such that for every edge:

u → v

u appears before v.

It is the standard abstraction for dependency ordering in build systems, course prerequisites, CI/CD jobs, workflows, ETL pipelines, module graphs, and many other systems.

The critical restriction is:

Topological sorting exists only for a DAG.

A DAG is a Directed Acyclic Graph.

Why cycles make ordering impossible

Suppose:

A → B
B → C
C → A

The constraints require:

A before B
B before C
C before A

which is impossible.

Therefore:

cycle → no valid topological order

Kahn's algorithm

Kahn's algorithm uses in-degree, the number of incoming edges to each vertex.

A vertex with in-degree zero has no unresolved prerequisites and can be processed immediately.

Steps

1. Compute every vertex's in-degree.
2. Put every zero-in-degree vertex into a queue.
3. Remove one vertex and append it to the result.
4. Decrease the in-degree of its outgoing neighbors.
5. Enqueue any neighbor whose in-degree becomes zero.
6. Continue until the queue is empty.
7. If fewer than V vertices were processed, the graph contains a cycle.

JavaScript

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

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

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

  const indegree = new Map();

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

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

  const queue = [];

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

  let head = 0;
  const order = [];

  while (head < queue.length) {
    const current = queue[head++];
    order.push(current);

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

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

  return order.length === nodes.size
    ? order
    : null;
}

Using a head index avoids repeated Array.shift() overhead in large JavaScript queues.

DFS-based topological sorting

A second standard method uses DFS.

The idea is to append a vertex only after all of its outgoing dependencies have been processed.

This creates a reverse finishing order.

A production implementation should also detect cycles using three states:

0 = unvisited
1 = visiting
2 = finished

JavaScript

function topologicalSortDFS(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 state = new Map();
  const order = [];

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

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

    state.set(node, 1);

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

    state.set(node, 2);
    order.push(node);

    return true;
  }

  for (const node of nodes) {
    if ((state.get(node) ?? 0) === 0) {
      if (!dfs(node)) return null;
    }
  }

  return order.reverse();
}

Kahn vs DFS

| Feature | Kahn | DFS | |---|---|---| | Core structure | Queue + in-degree | Recursion / stack | | Cycle detection | Processed count | Visiting state | | Iterative by nature | Yes | Usually recursive | | Dependency levels | Very convenient | Less direct | | Finish-order logic | No | Yes | | Stack-overflow risk | No | Recursive version can |

Both run in:

O(V + E)

with adjacency lists.

Multiple valid orders

Topological ordering is not necessarily unique.

For:

A → C
B → C

both:

A, B, C

and:

B, A, C

are valid.

This happens because there is no ordering constraint between A and B.

Unique topological order

In Kahn's algorithm, if there is more than one zero-in-degree choice at some stage, multiple valid orders may exist.

If exactly one choice exists at every step and the graph is acyclic, the order is unique.

Lexicographically smallest order

If several vertices are currently available and a deterministic smallest ordering is required, use a min-heap or priority queue instead of a normal queue.

Dependency levels and parallel execution

Kahn's algorithm can also group tasks by dependency level.

Example:

Level 0: Install
Level 1: Lint, Test
Level 2: Build
Level 3: Deploy

Tasks in the same level may be candidates for parallel execution if no other constraints exist.

Course prerequisites

If:

Programming → Data Structures
Data Structures → Algorithms
Algorithms → AI

then a valid order is:

Programming
→ Data Structures
→ Algorithms
→ AI

Adding:

AI → Programming

creates a cycle and makes the curriculum impossible.

Build systems

Build targets can be modeled as vertices and prerequisite relations as edges.

Topological sorting gives a valid build order.

CI/CD and workflows

Jobs can be scheduled only after their prerequisites have completed.

A DAG representation makes dependency validation, ordering, and parallel frontier detection straightforward.

ETL and data pipelines

Stages such as:

Extract
→ Clean
→ Aggregate
→ Train
→ Publish

naturally form a DAG.

Topological order determines execution order and exposes independent stages.

Shortest paths in DAGs

After topologically sorting a weighted DAG, edges can be relaxed in topological order.

This computes shortest paths in:

O(V + E)

even when some edge weights are negative, because DAGs contain no cycles.

Longest path in a DAG

Unlike general graphs, longest paths in DAGs can be solved efficiently with dynamic programming over a topological order.

This is useful in scheduling and critical-path analysis.

Partial orders

Topological sorting is different from ordinary sorting.

Dependencies define only a partial order.

Topological sorting produces a linear ordering consistent with that partial order.

Important edge cases

• empty graph,
• a single vertex,
• disconnected DAGs,
• vertices that appear only as destinations,
• self-loops,
• duplicate edges,
• very deep dependency chains.

A common implementation bug is using only Object.keys(graph) and forgetting destination-only vertices.

Real-world examples

• course scheduling,
• package and module dependencies,
• build systems,
• CI/CD jobs,
• workflow engines,
• ETL pipelines,
• spreadsheet formula recalculation,
• database migrations,
• infrastructure provisioning,
• DAG dynamic programming.

Complexity

Kahn:

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

DFS:

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

The graph itself requires O(V + E) storage with adjacency lists.

TypeScript

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

function topologicalSort(
  graph: Graph
): string[] | null {
  const nodes = new Set<string>();

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

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

  const indegree = new Map<string, number>();

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

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

  const queue: string[] = [];

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

  let head = 0;
  const order: string[] = [];

  while (head < queue.length) {
    const current = queue[head++];
    order.push(current);

    for (const next of graph[current] ?? []) {
      const value = (indegree.get(next) ?? 0) - 1;

      indegree.set(next, value);

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

  return order.length === nodes.size
    ? order
    : null;
}

Common mistakes

• running topological sorting on cyclic graphs,
• forgetting destination-only vertices,
• using DFS without cycle detection,
• assuming the order is unique,
• reversing dependency edge direction,
• confusing topological ordering with shortest-path computation,
• using recursive DFS on extremely deep graphs without considering stack limits.

Summary

Topological sorting answers dependency-order questions in a DAG.

Two standard approaches are:

Kahn
→ in-degree
→ queue

DFS
→ postorder
→ reverse finish order

Both run in O(V + E).

The key recognition pattern is:

Must some tasks happen before others?
Does a dependency graph need a valid execution order?
Do we need to validate that the dependencies are acyclic?

→ Topological Sorting