Topological Sorting (Only for Directed)

 

 

Topological sorting of a directed graph in graph theory is just a simple linear ordering of the nodes of the graph in such a way such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

 

Example:

 

Here one of the topologically sorted sequence can be

 

A,B,C,E,D,F.

 

To find a topologically sorted sequence, the following algorithm is used.

 

  1. We start from any vertex and apply a DFS on the node and start searching for all its childs.

 

  1. We do DFS on a certain node until all its child are visited (using

DFS method)

 

  1. After all the children of a the node are visited, we push that into a stack.

 

  1. Popping out the stack after visiting all nodes through this algorithm will give us the topologically sorted sequence.

 

#include<bits/stdc++.h> using namespace std; vector <int> v;

bool vis[100005];

vector < int > adj[100005];

void dfs(int x)

{

vis[x]=true;

for(auto i:adj[x])

{

if(!vis[i])

{

dfs(i);

}

}

v.push_back(x);

}

int main()

{

int n,m;

cin>>n>>m;

for(int i=0;i<m;i++)

{

int a,b; cin>>a>>b; adj[a].push_back(b);

}

memset(vis,false,sizeof(vis));

for(int i=1;i<=n;i++)

{

if(!vis[i])

{

dfs(i);

 

}

}

reverse(v.begin(),v.end());

cout<<"Topologically sorted sequence "<<endl;

for(auto i:v)

{

cout<<i<<" ";

}

cout<<endl;

}

 

Some Practice Problems

Happy Coding 😊

By Programmers Army