Topological Sort Using DFS
#include<bits/stdc++.h>
using namespace std;
class Graph{
int v;
list<int>*l;
public:
Graph(int v){
this->v=v;
l=new list<int>[v];
}
void addEdge(int x,int y){
l[x].push_back(y);
}
void topologicalSort(){
vector<bool>visited(v,false);
list<int>order;
for(int i=0; i<v; i++)if(!visited[i])dfs(i,visited,order);
for(int i:order)cout<<i<<"->";
}
void dfs(int node,vector<bool>&visited,list<int>&order){
visited[node]=true;
for(int nbr:l[node]){
if(!visited[nbr])dfs(nbr,visited,order);
}
order.push_front(node);
return;
}
};
int main(){
Graph g(6);
g.addEdge(0,2);
g.addEdge(1,2);
g.addEdge(2,3);
g.addEdge(3,5);
g.addEdge(4,5);
g.addEdge(1,4);
g.topologicalSort();
}
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.