Topological Sorting (Kahn's BFS-based Algorithm)

Topological Sorting for a Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge $u \rightarrow v$, vertex $u$ comes before $v$ in the ordering.

Topological sorting is only possible for Directed Acyclic Graphs (DAGs). It is widely used in task scheduling, resolving compile-time dependencies, and data serialization.

Kahn's Algorithm (BFS-based Approach)

Kahn's algorithm utilizes the concept of In-degree (the number of incoming edges to a vertex) to order the nodes.

Step-by-Step Algorithm

Calculate In-degrees: Compute the in-degree for every vertex in the graph.
Initialize Queue: Add all vertices with an in-degree of 0 (no incoming dependencies) to a queue.
Process Vertices:
- Dequeue a vertex $u$ from the queue and append it to the topological order list.
- For each adjacent neighbor $v$ of $u$, decrement its in-degree by 1.
- If the in-degree of $v$ becomes 0, enqueue $v$.
Repeat: Continue until the queue is empty.
Cycle Check: If the number of vertices in the final topological order is less than the total number of vertices $V$ in the graph, the graph contains a cycle, and topological sorting is impossible.

JavaScript Code Implementation

class Graph {
    constructor(verticesCount) {
        this.vertices = verticesCount;
        this.list = {};
    }
 
    addVertex(vertex) {
        if (!this.list[vertex]) this.list[vertex] = [];
    }
 
    addEdge(v1, v2) {
        this.addVertex(v1);
        this.addVertex(v2);
        this.list[v1].push(v2); // Directed edge v1 -> v2
    }
 
    // Kahn's Algorithm for Topological Sort
    topologicalSort() {
        const in_degree = {};
        const order = [];
        const queue = [];
 
        // Step 1: Initialize in-degrees of all vertices to 0
        Object.keys(this.list).forEach(vertex => {
            in_degree[vertex] = 0;
        });
 
        // Step 2: Compute in-degrees
        Object.keys(this.list).forEach(u => {
            const neighbors = this.list[u] || [];
            neighbors.forEach(v => {
                in_degree[v] = (in_degree[v] || 0) + 1;
            });
        });
 
        // Step 3: Enqueue all vertices with in-degree 0
        Object.keys(this.list).forEach(vertex => {
            if (in_degree[vertex] === 0) {
                queue.push(vertex);
            }
        });
 
        // Step 4: BFS processing loop
        while (queue.length > 0) {
            const u = queue.shift();
            order.push(u);
 
            const neighbors = this.list[u] || [];
            for (let v of neighbors) {
                in_degree[v]--;
                // If in-degree becomes 0, enqueue it
                if (in_degree[v] === 0) {
                    queue.push(v);
                }
            }
        }
 
        // Step 5: Check if there was a cycle
        if (order.length !== Object.keys(this.list).length) {
            console.log("Graph contains a cycle! Topological sort is not possible.");
            return [];
        }
 
        return order;
    }
}
 
// Driver code matching the example
const g = new Graph();
g.addEdge("5", "0");
g.addEdge("5", "2");
g.addEdge("4", "0");
g.addEdge("4", "1");
g.addEdge("2", "3");
g.addEdge("3", "1");
 
console.log("Topological Order:", g.topologicalSort().join(" "));
// Output: Topological Order: 5 4 2 0 3 1 (or 4 5 2 0 3 1)

Complexity Analysis

Time Complexity: $O(V + E)$
- We calculate in-degrees by scanning all edges: $O(E)$.
- We process each vertex once via the queue: $O(V)$.
Space Complexity: $O(V)$
- Storing the in_degree map, the queue, and the output topological order array requires linear space proportional to vertices.

Detect Cycle in Directed Graph Detect Cycle using Kahn's Algorithm