Example: Kahn's Algorithm for Topological Sort in C++

// Kahn's Algorithm for Topological Sort
#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

// Function to perform Kahn's algorithm for topological sort
vector<int> topologicalSortKahn(int numNodes, const vector<vector<int>>& adj) {
    // Step 1: Calculate in-degrees for all nodes
    map<int, int> inDegree;
    for (int i = 0; i < numNodes; ++i) {
        inDegree[i] = 0; // Initialize all nodes with in-degree 0
    }
    for (int u = 0; u < numNodes; ++u) {
        for (int v : adj[u]) {
            inDegree[v]++; // Increment in-degree for each neighbor
        }
    }

    // Step 2: Initialize queue with all nodes having in-degree 0
    queue<int> q;
    for (int i = 0; i < numNodes; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // Step 3: Process nodes from the queue
    vector<int> result;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u); // Add current node to topological order

        // For all neighbors of u, decrement their in-degree
        for (int v : adj[u]) {
            inDegree[v]--;
            // If a neighbor's in-degree becomes 0, add it to the queue
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // Step 4: Check for cycle (if result size is not equal to numNodes)
    if (result.size() != numNodes) {
        // This indicates a cycle in the graph, so topological sort is not possible.
        // For this example, we'll return an empty vector to signify this.
        return {}; 
    }

    return result;
}

int main() {
    // Example Graph (0->1, 0->2, 1->3, 2->3)
    // Nodes: 0, 1, 2, 3
    int numNodes = 4;
    vector<vector<int>> adj(numNodes);
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(3);

    cout << "Topological Sort using Kahn's Algorithm:" << endl;
    vector<int> sortedOrder = topologicalSortKahn(numNodes, adj);

    if (sortedOrder.empty() && numNodes > 0) { // Check if empty due to cycle or empty graph
        cout << "Graph contains a cycle, topological sort not possible." << endl;
    } else {
        for (int node : sortedOrder) {
            cout << node << " ";
        }
        cout << endl;
    }

    // Another Example Graph (5->0, 4->0, 5->2, 4->1, 2->3, 3->1)
    // Nodes: 0, 1, 2, 3, 4, 5
    numNodes = 6;
    adj.assign(numNodes, vector<int>()); // Clear and resize
    adj[5].push_back(0);
    adj[5].push_back(2);
    adj[4].push_back(0);
    adj[4].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(1);
    
    cout << "\nTopological Sort using Kahn's Algorithm (Another Example):" << endl;
    sortedOrder = topologicalSortKahn(numNodes, adj);

    if (sortedOrder.empty() && numNodes > 0) {
        cout << "Graph contains a cycle, topological sort not possible." << endl;
    } else {
        for (int node : sortedOrder) {
            cout << node << " ";
        }
        cout << endl;
    }

    return 0;
}