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 Sort is used to linearly order the vertices of a Directed Acyclic Graph (DAG) such that for every directed edge u → v, vertex u comes before v in the order. This is often used in scheduling problems, like task execution order based on dependencies.

We will solve this using Kahn’s Algorithm, which uses a Breadth-First Search (BFS) approach based on indegree counts.

Step-by-Step Solution with Example

Step 1: Represent the Graph

We represent the graph using an adjacency list and also track the indegree (number of incoming edges) for each node.

Example: Given edges: [[5, 0], [4, 0], [5, 2], [2, 3], [3, 1], [4, 1]]

This means:

5 → 0
4 → 0
5 → 2
2 → 3
3 → 1
4 → 1

Step 2: Compute Indegrees

We loop over all edges and count how many edges point to each vertex.

After processing the above edges, indegrees would look like:


0: 2
1: 2
2: 1
3: 1
4: 0
5: 0

Step 3: Initialize Queue

We add all vertices with indegree 0 to a queue. These are the starting points because they have no dependencies.

Queue: [4, 5]

Step 4: BFS Traversal

While the queue is not empty:

Dequeue a node and add it to the result.
For each of its neighbors, reduce their indegree by 1.
If a neighbor’s indegree becomes 0, add it to the queue.

Progress:


Queue: [4, 5] → [5, 0] → [0, 2] → [2, 3] → [3, 1] → [1]
Result: [4, 5, 0, 2, 3, 1]

Step 5: Check for Cycles

If at the end, the result does not contain all nodes, it means a cycle exists and topological sort is not possible. If the size of the result equals the number of vertices, we have a valid topological order.

Edge Cases

Case 1: Empty Graph

If the graph has no vertices, return an empty list. No work to be done.

Case 2: Single Node with No Edges

The output is simply the node itself.

Case 3: Multiple Starting Nodes

When multiple nodes have indegree 0, the result may vary depending on which is dequeued first. All are valid topological orders.

Case 4: Cycle in Graph

If there's a cycle, like 1 → 2 → 3 → 1, no topological sort is possible. Our result will have fewer nodes than expected, indicating a cycle.

Finally

Kahn’s Algorithm is a simple yet powerful way to solve topological sorting using a queue and indegree tracking. It not only provides the topological order but also helps in detecting cycles in the graph. This is especially useful in real-life applications like course prerequisites, task scheduling, and build systems.

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

Comments

Loading comments...