Graph Algorithms

Topological Sort

What is Topological Sort?

A topological sort takes a directed acyclic graph (a DAG — directed edges, no cycles) and arranges every vertex into a linear order such that, for every edge u → v, u appears before v in that order. Think of each edge as a "must come before" constraint: topological sort finds an order that satisfies every constraint at once. Multiple valid orders can exist for the same graph — the algorithm just needs to find one of them.

How Does Kahn's Algorithm Work?

Kahn's algorithm builds the order using each vertex's in-degree — the number of edges pointing into it, which represents "how many prerequisites are left." Any vertex with in-degree 0 has no unmet prerequisites, so it's safe to place next in the order right away. Whenever a vertex is placed, its outgoing edges are "removed" by decrementing the in-degree of everything it points to — which may free up new vertices to become in-degree 0 and get queued themselves.

That queue-driven process is exactly why the algorithm doubles as a cycle detector: if the graph really is acyclic, every vertex eventually reaches in-degree 0 and gets processed. But if a cycle exists, every vertex in that cycle keeps at least one unmet prerequisite forever — none of them can ever reach in-degree 0, so they're never queued. If the final order doesn't include every vertex, the graph must contain a cycle, and no valid topological order exists at all.

Getting dressed: Shirt and Pants have no prerequisites, so either can go first
Shirt1Belt3Pants2Shoes4

Algorithm Steps

  1. Compute the in-degree (number of incoming edges) for every vertex
  2. Initialize a queue with every vertex that already has in-degree 0
  3. While the queue isn't empty, repeat:
    • Dequeue a vertex and place it next in the output order
    • For each of its outgoing edges, decrement the target vertex's in-degree
    • If a target vertex's in-degree just reached 0, enqueue it
  4. If the final order includes every vertex, it's a valid topological order; if not, the graph contains a cycle

Time Complexity

  • Time Complexity: O(V + E) — every vertex is enqueued once and every edge is examined once during in-degree updates.
  • Space Complexity: O(V) — for the in-degree array and the queue.

Time Complexity Analysis

Advertisement

Topological sort is the standard tool for scheduling problems with dependencies: build systems compiling files in the right order, package managers installing dependencies before the packages that need them, course prerequisite planning, and task schedulers in project management tools that need to respect "this must finish before that starts" constraints.

Daily DSA Challenge by Scale Engineer

Order every vertex so each one comes after all of its prerequisites

Build a directed graph (a DAG) and run Topological Sort

Graph (Dependency DAG)

Add a vertex to begin
UnprocessedPlaced in orderCurrently processedStuck in a cycle

Test Your Knowledge before moving forward!

Topological Sort Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Topological Sort Implementation

// Kahn's algorithm: repeatedly process a vertex with no remaining
// prerequisites (in-degree 0), then decrement its neighbors' in-degrees --
// which may free them up to be processed too.
function topologicalSort(vertices, adjList) {
  const inDegree = {};
  vertices.forEach((v) => (inDegree[v] = 0));
  vertices.forEach((v) => (adjList[v] || []).forEach((to) => (inDegree[to] += 1)));

  const queue = vertices.filter((v) => inDegree[v] === 0);
  const order = [];

  while (queue.length > 0) {
    const u = queue.shift();
    order.push(u);

    for (const v of adjList[u] || []) {
      inDegree[v] -= 1;
      if (inDegree[v] === 0) queue.push(v);
    }
  }

  if (order.length < vertices.length) {
    throw new Error("Graph contains a cycle -- no valid topological order exists");
  }
  return order;
}

// Usage example
const adjList = { A: ["B", "C"], B: ["D"], C: ["D"], D: ["E"], E: [] };
topologicalSort(["A", "B", "C", "D", "E"], adjList); // ["A", "B", "C", "D", "E"]

Done With the Learning

Mark Topological Sort as done and view it on your dashboard

Explore Other Topics

Prim's Algorithm

Kruskal's Algorithm

Dijkstra's Algorithm

Depth-First Search