Topological Sort Using Kahn's Algorithm (BFS)

Problem Statement❯

Topological Sort of a directed graph is a linear ordering of its vertices such that for every directed edge u → v, vertex u comes before v in the ordering.

Kahn’s Algorithm uses a BFS-based approach and is suitable for Directed Acyclic Graphs (DAGs). It efficiently produces a valid topological ordering or detects the presence of a cycle.

Examples❯

Graph (Edges)	Topological Order	Description
[[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]	[4, 5, 2, 3, 1, 0]	Valid topological sort respecting all dependencies
[[0, 1], [1, 2], [2, 3]]	[0, 1, 2, 3]	Simple linear DAG
[]	[]	Empty graph has no vertices to sort
[[0, 1], [1, 0]]	null	Graph contains a cycle, so topological sort is not possible
[[1, 3], [2, 3], [3, 4]]	[1, 2, 3, 4]	Multiple valid orderings possible

Solution❯

Understanding the Problem

Topological sorting of a directed graph is a linear ordering of its vertices such that for every directed edge u → v, vertex u comes before v in the ordering. This is only possible if the graph has no cycles, i.e., it is a Directed Acyclic Graph (DAG).

Step-by-Step Explanation

We use Kahn's Algorithm, which is a breadth-first search (BFS) based approach. First, we calculate the indegree (number of incoming edges) for each vertex. Then we enqueue all vertices that have an indegree of 0, as these have no prerequisites and can safely be placed at the beginning of the ordering.

We then process the queue:

Remove a node u from the front of the queue and add it to the result list.
For each neighbor v of u, decrease its indegree by 1 because the edge u → v has now been 'used'.
If v's indegree becomes 0, it means all its prerequisites have been processed, and we enqueue v.

Cycle Detection

If, at the end, our result list does not contain all the vertices, it means there is a cycle in the graph. The cycle prevents some nodes from ever reaching an indegree of 0, thus making topological sort impossible. In that case, we return null.

Different Cases

Case 1: Normal DAG

Suppose we have a graph with a clear hierarchy of dependencies (like a build system). Kahn’s algorithm will give us one of the valid topological orderings that obey all constraints.

Case 2: Multiple Valid Orders

When more than one node has an indegree of 0 at the same time, the order of their insertion into the queue can vary, leading to multiple valid topological sorts.

Case 3: Graph with a Cycle

If there’s a cycle (like 1 → 2 → 3 → 1), no node in the cycle will ever reach an indegree of 0 after initialization. The queue becomes empty before we process all nodes. Thus, the result list will not include all vertices, and we detect the cycle.

Algorithm Steps❯

Compute the indegree of each vertex.
Initialize a queue and enqueue all vertices with indegree 0.
Initialize an empty list to store the topological order.
While the queue is not empty:

Dequeue a vertex u and add it to the result list.
For each neighbor v of u:

Decrease indegree[v] by 1.
If indegree[v] == 0, enqueue v.

If the result contains all vertices, return the result.
Else, return null (cycle detected).

Code

JavaScript

function topologicalSortKahn(V, edges) {
  const indegree = Array(V).fill(0);
  const graph = Array.from({ length: V }, () => []);
  const result = [];

  for (const [u, v] of edges) {
    graph[u].push(v);
    indegree[v]++;
  }

  const queue = [];
  for (let i = 0; i < V; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    for (const neighbor of graph[node]) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

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

const V = 6;
const edges = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]];
console.log("Topological Sort:", topologicalSortKahn(V, edges));

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(V + E)	Even in the best case, we must visit all vertices and all edges once to compute indegrees and process the graph structure.
Average Case	O(V + E)	For any valid DAG, each vertex and edge is processed exactly once.
Worst Case	O(V + E)	Regardless of graph structure (as long as it is a DAG), we always have to check every node and every edge at least once.

Space Complexity❯

O(V + E)

Explanation: We use additional space for the adjacency list (O(E)), indegree array (O(V)), the queue (O(V)), and result list (O(V)).

⬅ Previous TopicTopological Sort Using DFS

Next Topic ⮕Cycle Detection in Directed Graph using BFS