Topological Sorting in Graphs

Topological sorting is a graph algorithm used to arrange the vertices of a directed graph in an order where every directed edge u → v places u before v.

Topological sorting is useful when tasks, modules, courses, or other entities have dependencies. For example, if task A must be completed before task B, a topological ordering places A before B.

A topological ordering exists only for a Directed Acyclic Graph (DAG). If the directed graph contains a cycle, there is no valid topological ordering because the cycle creates a circular dependency.

What Is Topological Sorting?

Consider the following dependency graph:

A → C
B → C
C → D

A valid topological ordering is:

A → B → C → D

Another valid ordering can be B → A → C → D. Both are correct because A and B do not depend on one another, while both must appear before C, and C must appear before D.

Important Rule

This rule is the foundation of every topological sorting algorithm.

Topological Sorting Example

Suppose a developer must complete the following tasks:

Requirements → Design
Design       → Development
Development  → Testing
Testing      → Deployment

A valid execution order is:

Requirements
    ↓
Design
    ↓
Development
    ↓
Testing
    ↓
Deployment

The dependency relationships naturally define a directed graph, and topological sorting produces an order that respects those dependencies.

When Is Topological Sorting Possible?

Topological sorting is defined for a directed acyclic graph.

Consider this graph:

A → B → C

It has no cycle, so a topological ordering exists.

Now consider:

A → B → C
↑       ↓
└───────┘

Here, the vertices form a cycle. A would need to appear before B, B before C, and C before A. These requirements cannot all be satisfied, so no topological ordering exists.

Method 1: Topological Sorting Using Kahn's Algorithm

Kahn's algorithm uses the indegree of each vertex. The indegree is the number of directed edges entering a vertex.

The main idea is:

1. Calculate the indegree of every vertex.
2. Add all vertices with indegree 0 to a queue.
3. Remove a vertex from the queue and add it to the result.
4. Reduce the indegree of each outgoing neighbor.
5. If a neighbor's indegree becomes 0, add it to the queue.
6. Continue until the queue is empty.
7. If every vertex was processed, the result is a topological ordering.
8. If some vertices remain unprocessed, the graph contains a cycle.

Understanding Indegree

Consider:

A → C
B → C
C → D

The indegrees are:

A and B can be processed first because neither has an unresolved prerequisite.

Kahn's Algorithm Implementation

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

  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 index = 0;

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

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

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

  if (result.length !== Object.keys(graph).length) {
    return null;
  }

  return result;
}

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

console.log(topologicalSort(graph));

Returning null in this implementation indicates that the graph contains a cycle and therefore has no valid topological ordering.

Kahn's Algorithm Step by Step

For the graph:

A → C
B → C
C → D

1. A and B have indegree 0, so both enter the queue.
2. Remove A and add it to the result.
3. C's indegree decreases from 2 to 1.
4. Remove B and add it to the result.
5. C's indegree decreases from 1 to 0.
6. C enters the queue.
7. Remove C and add it to the result.
8. D's indegree becomes 0.
9. Remove D and add it to the result.

One possible result is [A, B, C, D].

Method 2: Topological Sorting Using DFS

Topological sorting can also be performed using Depth-First Search. The key idea is to add a vertex to a stack after all of its outgoing neighbors have been processed.

For a directed graph, DFS also needs to detect cycles. A three-state system is commonly used:

If DFS reaches a vertex whose state is 1, it has found an edge back to the current recursion path. That indicates a cycle.

DFS Topological Sort Implementation

function topologicalSort(graph) {
  const state = {};
  const stack = [];

  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 false;
      }

      if (state[neighbor] === 0) {
        if (!dfs(neighbor)) {
          return false;
        }
      }
    }

    state[node] = 2;
    stack.push(node);

    return true;
  }

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

  return stack.reverse();
}

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

console.log(topologicalSort(graph));

A vertex is pushed onto the stack only after all reachable dependencies have been processed. Reversing the stack produces a valid topological ordering.

Why DFS Adds Vertices After Processing

Consider:

A → B → C

DFS starts at A and reaches B, then C. C has no outgoing edges, so C is pushed first. Then B is pushed, followed by A.

Stack:
C
B
A

Reverse:
A → B → C

This post-order processing is what makes the DFS approach suitable for topological sorting.

Topological Sort and Cycle Detection

Cycle detection is an essential part of topological sorting because a directed cycle makes the ordering impossible.

A → B
B → C
C → A

There is no vertex that can satisfy all three ordering constraints. A would need to appear before B, B before C, and C before A. Therefore, the graph is not a DAG and has no topological ordering.

Detecting a Cycle with Kahn's Algorithm

Kahn's algorithm can detect a cycle without using a separate cycle-detection routine. If the algorithm cannot process every vertex, a cycle exists.

function hasCycle(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(hasCycle(graph)); // true

Multiple Valid Topological Orders

A graph can have more than one valid topological ordering. Topological sorting does not necessarily produce a unique result.

A → C
B → C

Both of these are valid:

A → B → C

B → A → C

A and B have no dependency relationship with each other, so their relative order can change as long as both appear before C.

Topological Sorting with Numeric Vertices

The same algorithm can be implemented using numeric vertex identifiers and adjacency lists.

function topologicalSort(graph, vertices) {
  const indegree = new Array(vertices).fill(0);
  const queue = [];
  const result = [];

  for (let node = 0; node < vertices; node++) {
    for (const neighbor of graph[node]) {
      indegree[neighbor]++;
    }
  }

  for (let node = 0; node < vertices; node++) {
    if (indegree[node] === 0) {
      queue.push(node);
    }
  }

  let index = 0;

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

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

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

  return result.length === vertices
    ? result
    : null;
}

const graph = [
  [1, 2],
  [3],
  [3],
  []
];

console.log(topologicalSort(graph, 4));

Topological Sorting for Course Prerequisites

Course scheduling is a common application. Suppose a student must complete one course before another:

Programming Fundamentals → Data Structures
Data Structures       → Algorithms
Algorithms            → Advanced Algorithms

A topological ordering can produce a valid sequence in which the prerequisites are satisfied before dependent courses.

Topological Sorting for Build Systems

Software projects often contain dependencies between modules or build tasks. For example:

Core → Authentication
Core → Database
Authentication → API
Database → API

A dependency-aware build system can use a topological ordering to determine an order in which independent tasks can be processed while respecting prerequisites.

Topological Sorting for Task Scheduling

Task scheduling problems can also be modeled as directed graphs. If one task depends on another, the dependency becomes a directed edge.

Plan → Code
Code → Test
Code → Review
Test → Deploy
Review → Deploy

Topological sorting can produce an order that respects all these relationships. Independent tasks such as Test and Review may appear in either order unless another dependency specifies their relationship.

DFS vs Kahn's Algorithm

Time and Space Complexity

For an adjacency-list representation, both common topological sorting approaches process every vertex and edge a bounded number of times.

Time Complexity: O(V + E)

Where:

• V is the number of vertices.
• E is the number of directed edges.

Additional space is typically O(V) for the queue, stack, state information, indegree array, and result. The graph representation itself requires additional storage.

Topological Sorting with an Adjacency Matrix

If the graph is represented using an adjacency matrix, identifying all outgoing neighbors of a vertex may require scanning an entire row. This can result in O(V²) graph-processing work.

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

For sparse dependency graphs, adjacency lists are generally a more natural representation because only existing edges need to be stored and examined.

Topological Sort vs Normal Sorting

Topological sorting is different from sorting numbers or strings using a comparison operation.

Traditional sorting arranges values according to an ordering rule such as numeric or alphabetical order. Topological sorting arranges vertices according to dependency relationships represented by directed edges.

Common Beginner Mistakes

• Trying to topologically sort an undirected graph.
• Ignoring cycles in a directed graph.
• Forgetting to include vertices that have no outgoing edges.
• Calculating indegree incorrectly.
• Adding a DFS vertex to the result before processing its dependencies.
• Assuming a topological ordering is always unique.
• Using only one starting vertex and ignoring disconnected portions of the graph.
• Confusing topological ordering with numerical or alphabetical sorting.

Interview Pattern to Remember

When a problem contains phrases such as "must be completed before", "prerequisite", "dependency", or "valid ordering", consider modeling it as a directed graph.

Then ask:

1. Are the relationships directed?
2. Can the dependencies contain a cycle?
3. Do I need one valid ordering or to determine whether ordering is possible?
4. Would DFS or Kahn's algorithm fit the problem better?

Key Takeaways

• Topological sorting orders the vertices of a directed graph according to dependency relationships.
• For every edge u → v, u must appear before v.
• Topological sorting is possible only for a Directed Acyclic Graph (DAG).
• Kahn's algorithm uses indegrees and a queue.
• DFS-based topological sorting uses post-order processing and a stack.
• Both common approaches have O(V + E) time complexity with an adjacency-list representation.
• Cycle detection is essential because a directed cycle makes topological ordering impossible.
• A graph can have multiple valid topological orderings.
• Topological sorting is useful for dependencies, course prerequisites, task scheduling, and build systems.