C++ Online Compiler
Example: Kahn's Algorithm for Topological Sort in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// 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; }
Output
Clear
ADVERTISEMENTS