C++ Online Compiler
Example: DFS-based Topological Sort in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// DFS-based Topological Sort #include <iostream> #include <vector> #include <stack> #include <list> // For adjacency list using namespace std; // Graph class to represent a directed graph class Graph { int V; // Number of vertices list<int>* adj; // Pointer to an array containing adjacency lists // A recursive function used by topologicalSort void topologicalSortUtil(int v, vector<bool>& visited, stack<int>& Stack) { // Mark the current node as visited visited[v] = true; // Recur for all the vertices adjacent to this vertex for (int neighbor : adj[v]) { if (!visited[neighbor]) { topologicalSortUtil(neighbor, visited, Stack); } } // Push current vertex to stack which stores result Stack.push(v); } public: Graph(int V) { this->V = V; adj = new list<int>[V]; } // Function to add an edge to graph void addEdge(int u, int v) { adj[u].push_back(v); } // Prints a topological sort of the complete graph void topologicalSort() { stack<int> Stack; vector<bool> visited(V, false); // Mark all the vertices as not visited // Call the recursive helper function for all vertices // to get topological sort for (int i = 0; i < V; i++) { if (!visited[i]) { topologicalSortUtil(i, visited, Stack); } } // Print contents of stack cout << "Topological Sort (DFS-based): "; while (!Stack.empty()) { cout << Stack.top() << " "; Stack.pop(); } cout << endl; } }; int main() { // Step 1: Create a graph Graph g(6); // 6 vertices (0 to 5) // Step 2: Add edges representing dependencies g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); // Step 3: Perform topological sort g.topologicalSort(); return 0; }
Output
Clear
ADVERTISEMENTS