Question

write a program for topological ordering of a graph in c/c++ programming. The input contains a list of adjacent list of a directed acyclic graph. The output is a topological ordering of verticies.

Answer 1

This problem is solved using dfs with slight modification.After a vertex is visited it is not immediately pushed in stack like in dfs .but first its all unvisited adjacent vertices are visited then the vertex is pushed in stack

More explanation through source code

#include <bits/stdc++.h>
using namespace std;
void topoHelp(list<int> l[],int v,bool visited[],stack<int> &s)
{
   //make the visited of v as true
   visited[v]=true;
   list<int>::iterator i;
   //iterate through all the adajecent nodes of v
   //if any is unvivited call topoHelp for that vertex
   for(i=l[v].begin();i!=l[v].end();++i)
   {
       if(visited[*i]==false)
       topoHelp(l,*i,visited,s);
   }
   //finally push v in stack
   s.push(v);
   return;
}
void topologicalSort(list<int> l[],int v)
{
   //make a visited function
   bool visited[v];
   //initialise it to false
   memset(visited,false,sizeof(visited));
   //make a temp stack
   stack<int> s;
   //for all unvisited nodes call topoHelp
   for(int i=0;i<v;i++)
   {
       if(visited[i]==false)
       topoHelp(l,i,visited,s);
   }
   //print the contents of stack
   while(!s.empty())
   {
       cout<<s.top()<<" ";
       s.pop();
   }
   cout<<endl;
   return;
}

//testing
int main() {
   //number of vertices in graph
   int v=6;
   list<int> l[6];
   l[5].push_back(2);
   l[5].push_back(0);
   l[4].push_back(0);
   l[4].push_back(1);
   l[2].push_back(3);
   l[3].push_back(1);
   topologicalSort(l,6);
   return 0;
}

If need more help regarding this connect in comment section.please do upvote