Kahn's Algorithm

//kahn's.cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void kahns(vector<vector<int>>&adjlist,vector<int> &indegree){
queue<int> q;
for(int i=0;i<indegree.size();i++){
    if(indegree[i]==0){
        q.push(i);
    }
}
while(!q.empty()){
    int node=q.front();
    q.pop();
    cout<<node<<" ";
    for(int &v:adjlist[node]){
        indegree[v]--;
        if(indegree[v]==0){
            q.push(v);
        }
    }
}
}
int main()
{
int vertex, edge;
cin >> vertex >> edge;
vector<vector<int>> adjlist(vertex);
int u, v;
for (int i = 0; i < edge; i++)
{
    cin >> u >> v;
    adjlist[u].push_back(v);
}
vector<int> indegree(vertex);
for(int i=0;i<vertex;i++){
    for(int &v:adjlist[i]){
        indegree[v]++;
    }
}
kahns(adjlist,indegree);
}

# kahns_algorithm.py
from collections import deque

def kahns_algorithm(adj_list, num_vertices):
 """
 Kahn's algorithm for topological sorting using BFS approach
 """
 # Calculate indegree for each vertex
 indegree = [0] * num_vertices
 for u in range(num_vertices):
     for v in adj_list[u]:
         indegree[v] += 1
 
 # Initialize queue with vertices having 0 indegree
 queue = deque()
 for i in range(num_vertices):
     if indegree[i] == 0:
         queue.append(i)
 
 topo_order = []
 
 # Process vertices in BFS manner
 while queue:
     node = queue.popleft()
     topo_order.append(node)
     
     # Decrease indegree of adjacent vertices
     for neighbor in adj_list[node]:
         indegree[neighbor] -= 1
         if indegree[neighbor] == 0:
             queue.append(neighbor)
 
 # Check if topological sort is possible (no cycles)
 if len(topo_order) != num_vertices:
     return []  # Graph has a cycle
 
 return topo_order

# Example usage
if __name__ == "__main__":
 # Example: DAG with 6 vertices
 num_vertices = 6
 adj_list = [
     [2, 3],    # 0 -> 2, 3
     [3, 4],    # 1 -> 3, 4
     [5],       # 2 -> 5
     [4, 5],    # 3 -> 4, 5
     [5],       # 4 -> 5
     []         # 5 -> none
 ]
 
 result = kahns_algorithm(adj_list, num_vertices)
 
 if result:
     print("Topological Order:", result)
 else:
     print("Graph contains a cycle - topological sort not possible")

# Output: Topological Order: [0, 1, 2, 3, 4, 5]

 // kahns_algorithm.js
function kahnsAlgorithm(adjList, numVertices) {
 /**
  * Kahn's algorithm for topological sorting using BFS approach
  */
 // Calculate indegree for each vertex
 const indegree = new Array(numVertices).fill(0);
 for (let u = 0; u < numVertices; u++) {
     for (const v of adjList[u]) {
         indegree[v]++;
     }
 }
 
 // Initialize queue with vertices having 0 indegree
 const queue = [];
 for (let i = 0; i < numVertices; i++) {
     if (indegree[i] === 0) {
         queue.push(i);
     }
 }
 
 const topoOrder = [];
 
 // Process vertices in BFS manner
 while (queue.length > 0) {
     const node = queue.shift();
     topoOrder.push(node);
     
     // Decrease indegree of adjacent vertices
     for (const neighbor of adjList[node]) {
         indegree[neighbor]--;
         if (indegree[neighbor] === 0) {
             queue.push(neighbor);
         }
     }
 }
 
 // Check if topological sort is possible (no cycles)
 if (topoOrder.length !== numVertices) {
     return []; // Graph has a cycle
 }
 
 return topoOrder;
}

// Example usage
function main() {
 // Example: DAG with 6 vertices
 const numVertices = 6;
 const adjList = [
     [2, 3],    // 0 -> 2, 3
     [3, 4],    // 1 -> 3, 4
     [5],       // 2 -> 5
     [4, 5],    // 3 -> 4, 5
     [5],       // 4 -> 5
     []         // 5 -> none
 ];
 
 const result = kahnsAlgorithm(adjList, numVertices);
 
 if (result.length > 0) {
     console.log("Topological Order:", result);
 } else {
     console.log("Graph contains a cycle - topological sort not possible");
 }
}

main();

// Output: Topological Order: [0, 1, 2, 3, 4, 5]