C++ Program implementing Topological Sort using DFS
Topological sort using DFS
Description:
Topological Sort is a linear ordering of the vertices in such a way that if there is an edge in the DAG(Directed Acyclic Graph) going from vertex 'u' to vertex 'v', then 'u' comes before 'v' in the ordering.
Note:
- Topological Sorting is possible if and only if the graph is a Directed Acyclic Graph.
- There may exist multiple different topological orderings for a given directed acyclic graph.
Applications of Topological Sort:
- Scheduling jobs from the given dependencies among jobs
- Instruction Scheduling
- Determining the order of compilation tasks to perform
- Data Serialization
Code:
Topological Sort can be implemented using DFS
Time Complexity: O(V+E)
Space Complexity: O(V)
where V=number of vertices and E=number of edges
#include<iostream>
#include<map>
#include<vector>
#include<queue>
#include<list>
using namespace std;
class Graph{
map<int, vector<int> > adjlist;
map<int, bool> vis;
list<int> order;
public:
Graph(){
}
void addEdge(int u, int v){
adjlist[u].push_back(v);
}
void dfshelper(int u){
vis[u] = true;
for(auto i : adjlist[u]){
if(!vis[i])
dfshelper(i);
}
order.push_front(u);
}
void topological_dfs(){
for(auto i : adjlist){
int node = i.first;
if(!vis[node]){
dfshelper(node);
}
}
print_order();
}
void print_order(){
for(auto ele : order)
cout << ele << " -> ";
}
};
int main(){
Graph g;
g.addEdge(1,2);
g.addEdge(1,3);
g.addEdge(2,4);
g.addEdge(3,4);
g.topological_dfs();
return 0;
}Output:
1 -> 3 -> 2 -> 4
Comments