C++ Program implementing Topological Sort using DFS














































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