Kahn's Algorithm | Topological Sort Algorithm | BFS

Topological Sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge $U \to V$, vertex $U$ comes before vertex $V$ in the ordering. While Depth First Search (DFS) can compute a topological sort, this chapter explores the breadth-first traversal variant famously known as Kahn's Algorithm, which utilizes in-degrees and a Queue.

1. What is Topological Sorting?

Topological sort is strictly defined for Directed Acyclic Graphs (DAGs).

• Linear Ordering: A sequence of vertices $v_1, v_2, \dots, v_n$ representing the graph.
• Edge Rule: For every directed edge from node $U$ to node $V$, $U$ must appear before $V$ in the linear sequence.

Real-Life Analogy: Course Prerequisites

Analogy: Think of university course prerequisites. You cannot take Advanced Machine Learning ($V$) until you have completed Linear Algebra ($U$). Therefore, Linear Algebra must appear before Advanced Machine Learning in your graduation course schedule. If there were a circular prerequisite (Course A requires B, B requires C, and C requires A), you would experience a deadlock and could never graduate—this mirrors an invalid graph with a cycle.

2. Why DAGs Only? (Directed Acyclic Graphs)

Topological sort fails or is impossible in two specific graph structures:

1. Undirected Graphs: An undirected edge between $1$ and $2$ implies both $1 \to 2$ and $2 \to 1$. A linear sequence cannot simultaneously place $1$ before $2$ and $2$ before $1$.
2. Cyclic Graphs (Graphs with Cycles): If a graph contains a cycle ($1 \to 2 \to 3 \to 1$), node $1$ must precede node $2$, node $2$ must precede node $3$, and node $3$ must precede node $1$. This creates an impossible circular dependency.

Thus, the graph must be both Directed and Acyclic (DAG).

3. The Core Mental Model: In-Degree

Kahn's Algorithm introduces a critical metric: In-Degree.

• Definition: The number of incoming directed edges pointing directly to a given node.
• Example Graph Analysis: Consider a graph with nodes [0, 1, 2, 3, 4, 5] and edges:
  • 5 -> 0, 4 -> 0, 5 -> 2, 4 -> 1, 2 -> 3, 3 -> 1

Let's compute the initial in-degrees for each node:

• Node 0: Incoming from 5 and 4 $\rightarrow$ In-Degree = 2
• Node 1: Incoming from 4 and 3 $\rightarrow$ In-Degree = 2
• Node 2: Incoming from 5 $\rightarrow$ In-Degree = 1
• Node 3: Incoming from 2 $\rightarrow$ In-Degree = 1
• Node 4: Incoming from none $\rightarrow$ In-Degree = 0
• Node 5: Incoming from none $\rightarrow$ In-Degree = 0

4. Naive vs. Kahn's Algorithm Approach

5. Step-by-Step Execution of Kahn's Algorithm

Kahn's algorithm simulates the removal of independent nodes (in-degree of 0) layer by layer.

Initial State:
In-Degree Array: [0:2, 1:2, 2:1, 3:1, 4:0, 5:0]
Queue: [4, 5] (Nodes with in-degree 0)
Topo Sort Result: []

Step 1: Process Node 4

• Pop 4 from Queue. Add 4 to Topo Result ([4]).
• Examine neighbors of 4 (0 and 1).
• Reduce their in-degrees by 1:
  • In-degree of 0 drops from $2 \rightarrow 1$
  • In-degree of 1 drops from $2 \rightarrow 1$

Step 2: Process Node 5

• Pop 5 from Queue. Add 5 to Topo Result ([4, 5]).
• Examine neighbors of 5 (0 and 2).
• Reduce their in-degrees by 1:
  • In-degree of 0 drops from $1 \rightarrow 0$ (Queue pushes 0)
  • In-degree of 2 drops from $1 \rightarrow 0$ (Queue pushes 2)
• Queue is now: [0, 2]

Step 3: Process Node 0

• Pop 0 from Queue. Add 0 to Topo Result ([4, 5, 0]).
• Node 0 has no outgoing edges.

Step 4: Process Node 2

• Pop 2 from Queue. Add 2 to Topo Result ([4, 5, 0, 2]).
• Examine neighbor 3. Reduce in-degree of 3 from $1 \rightarrow 0$ (Queue pushes 3).
• Queue is now: [3]

Step 5: Process Node 3

• Pop 3 from Queue. Add 3 to Topo Result ([4, 5, 0, 2, 3]).
• Examine neighbor 1. Reduce in-degree of 1 from $1 \rightarrow 0$ (Queue pushes 1).
• Queue is now: [1]

Step 6: Process Node 1

• Pop 1 from Queue. Add 1 to Topo Result ([4, 5, 0, 2, 3, 1]).
• Node 1 has no outgoing edges. Queue is empty.

Final Valid Topological Sort: [4, 5, 0, 2, 3, 1] (Note: Other valid orderings like [5, 4, 2, 0, 3, 1] are also correct).

6. Complete Code Implementation

Below are the production-ready implementations in C++ and Java demonstrating Kahn's Algorithm.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> topologicalSort(vector<vector<int>>& adj, int V) {
        vector<int> indegree(V, 0);
        
        // Step 1: Calculate in-degrees for all nodes
        for (int i = 0; i < V; i++) {
            for (auto it : adj[i]) {
                indegree[it]++;
            }
        }
        
        // Step 2: Push all nodes with in-degree 0 into the queue
        queue<int> q;
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> topo;
        // Step 3: BFS traversal
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            
            topo.push_back(node);
            
            // Get neighbors and reduce their in-degree by 1
            for (auto it : adj[node]) {
                indegree[it]--;
                // If in-degree becomes 0, add to queue
                if (indegree[it] == 0) {
                    q.push(it);
                }
            }
        }
        
        return topo;
    }
};

Java Implementation

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int[] topologicalSort(List<List<Integer>> adj, int V) {
        int[] indegree = new int[V];
        
        // Step 1: Calculate in-degrees for all nodes
        for (int i = 0; i < V; i++) {
            for (int neighbor : adj.get(i)) {
                indegree[neighbor]++;
            }
        }
        
        // Step 2: Push all nodes with in-degree 0 into the queue
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) {
                q.add(i);
            }
        }
        
        int[] topo = new int[V];
        int index = 0;
        
        // Step 3: BFS traversal
        while (!q.isEmpty()) {
            int node = q.poll();
            topo[index++] = node;
            
            // Get neighbors and reduce their in-degree by 1
            for (int neighbor : adj.get(node)) {
                indegree[neighbor]--;
                // If in-degree becomes 0, add to queue
                if (indegree[neighbor] == 0) {
                    q.add(neighbor);
                }
            }
        }
        
        return topo;
    }
}

7. Complexity Analysis

• Time Complexity: $\mathcal{O}(V + E)$
  • Calculating in-degrees requires visiting every vertex and edge: $\mathcal{O}(V + E)$.
  • Pushing and popping every vertex from the queue takes $\mathcal{O}(V)$.
  • Traversing all adjacency lists during BFS takes $\mathcal{O}(E)$.
• Space Complexity: $\mathcal{O}(V)$
  • The indegree array takes $\mathcal{O}(V)$ space.
  • The Queue holds at most $V$ elements in the worst case: $\mathcal{O}(V)$.
  • The resultant storage array takes $\mathcal{O}(V)$ space.

Summary and Key Takeaways

• Topological Sort Definition: A linear ordering of DAG vertices such that every directed edge $U \to V$ ensures $U$ appears before $V$.
• Graph Constraint: Valid exclusively for Directed Acyclic Graphs (DAGs). Undirected graphs or graphs with cycles will fail.
• Core Concept (In-Degree): In-degree measures the number of incoming edges pointing to a node.
• Starting Point: Nodes with an in-degree of 0 have no prerequisites and serve as the starting seeds for the algorithm.
• Queue Mechanics: Kahn's Algorithm is a specialized BFS where nodes are pushed into a Queue only when their in-degree drops to 0.
• Edge Reduction: As each node is popped from the queue, its outgoing edges are conceptually "removed" by decrementing the in-degree of its adjacent neighbors.
• Time Efficiency: Runs in optimal linear time $\mathcal{O}(V + E)$, making it extremely efficient for large dependency graphs.