Topological Sort

Learn two algorithms for topological ordering of directed acyclic graphs — Kahn's BFS-based in-degree approach and the DFS finish-time approach — and understand why cycles make it impossible.

6 min read Level 3/5 #dsa#graph#topological-sort

What you'll learn

Implement Kahn's algorithm using a queue of zero-in-degree vertices
Implement the DFS finish-time approach to topological sorting
Explain why topological sort is only defined for DAGs

A topological sort arranges the vertices of a directed acyclic graph (DAG) in a linear order such that for every directed edge u → v, vertex u comes before v. Build systems, course prerequisites, and package dependency resolvers all rely on topological ordering.

Topological sort is undefined for graphs with cycles — there is no way to order a cycle so all edges point forward.

Kahn’s Algorithm (BFS on In-Degrees)

Kahn’s algorithm repeatedly removes vertices with no incoming edges, which are safe to place first in the order.

// graph: Map<number, Set<number>> (directed)
function kahnSort(graph, numVertices) {
  const inDegree = new Array(numVertices).fill(0);
  for (const [, neighbours] of graph) {
    for (const v of neighbours) inDegree[v]++;
  }

  const queue = [];
  for (let v = 0; v < numVertices; v++) {
    if (inDegree[v] === 0) queue.push(v);
  }

  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);

    for (const neighbour of graph.get(node) ?? []) {
      inDegree[neighbour]--;
      if (inDegree[neighbour] === 0) queue.push(neighbour);
    }
  }

  if (order.length !== numVertices) throw new Error("Graph has a cycle");
  return order;
}

// DAG: 5→0, 5→2, 4→0, 4→1, 2→3, 3→1
const g = new Map([
  [5, new Set([0, 2])],
  [4, new Set([0, 1])],
  [2, new Set([3])],
  [3, new Set([1])],
  [0, new Set()],
  [1, new Set()],
]);
console.log(kahnSort(g, 6)); // e.g. [4, 5, 0, 2, 3, 1]

The cycle check is free: if the final order is shorter than numVertices, some vertices were never reachable via in-degree reduction, meaning a cycle prevented them from ever reaching zero.

DFS Finish-Time Approach

Run DFS; when a vertex is fully explored (all descendants visited), prepend it to the result list. Vertices with no outgoing edges finish first and land at the end of the list, giving a valid topological order when the list is reversed at the end.

function dfsTopoSort(graph, numVertices) {
  const visited = new Set();
  const result = [];

  function dfs(v) {
    visited.add(v);
    for (const w of graph.get(v) ?? []) {
      if (!visited.has(w)) dfs(w);
    }
    result.push(v); // push after all descendants are done
  }

  for (let v = 0; v < numVertices; v++) {
    if (!visited.has(v)) dfs(v);
  }

  return result.reverse();
}

Comparison

Aspect	Kahn’s (BFS)	DFS finish-time
Cycle detection	Built-in (order check)	Needs separate logic
Implementation	Iterative	Recursive or iterative
Multiple orderings	Yes	Yes
Complexity	O(V+E)	O(V+E)

Both algorithms run in O(V+E). Kahn’s is often preferred in practice because cycle detection is automatic and the iterative form avoids stack overflow.

Up Next

Apply topological ideas to weighted graphs — Dijkstra’s algorithm finds the shortest path when all weights are non-negative.

Dijkstra's Shortest Path →