Pappu19

Topological_Sort

Mar 19th, 2019
101
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include <list>
  3. #include <stack>
  4. using namespace std;
  5.  
  6. // Class to represent a graph
  7. class Graph
  8. {
  9.     int V;
  10.     int Count=0;   // No. of vertices'
  11.  
  12.     // Pointer to an array containing adjacency listsList
  13.     list<int> *adj;
  14.  
  15.     // A function used by topologicalSort
  16.     void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
  17. public:
  18.     Graph(int V);   // Constructor
  19.  
  20.     // function to add an edge to graph
  21.     void addEdge(int v, int w);
  22.  
  23.     // prints a Topological Sort of the complete graph
  24.     void topologicalSort();
  25. };
  26.  
  27. Graph::Graph(int V)
  28. {
  29.     this->V = V;
  30.     adj = new list<int>[V];
  31. }
  32.  
  33. void Graph::addEdge(int v, int w)
  34. {
  35.     adj[v].push_back(w); // Add w to v’s list.
  36. }
  37.  
  38. // A recursive function used by topologicalSort
  39. void Graph::topologicalSortUtil(int v, bool visited[],
  40.                                 stack<int> &Stack)
  41. {
  42.     // Mark the current node as visited.
  43.     visited[v] = true;
  44.  
  45.     // Recur for all the vertices adjacent to this vertex
  46.     list<int>::iterator i;
  47.     Count++;
  48.     cout<<"Count = "<<Count<<endl;
  49.  
  50.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  51.     {
  52.         //cout <<"Hello "<< *i<< endl;
  53.         if (!visited[*i])
  54.             topologicalSortUtil(*i, visited, Stack);
  55.     }
  56.     //cout << "Hello vai"<<endl;
  57.     // Push current vertex to stack which stores result
  58.     Stack.push(v);
  59.     Count++;
  60.     cout<<"Count = "<<Count<<endl;
  61. }
  62.  
  63. // The function to do Topological Sort. It uses recursive
  64. // topologicalSortUtil()
  65. void Graph::topologicalSort()
  66. {
  67.     stack<int> Stack;
  68.  
  69.     // Mark all the vertices as not visited
  70.     bool *visited = new bool[V];
  71.  
  72.     for (int i = 0; i < V; i++)
  73.         visited[i] = false;
  74.  
  75.     // Call the recursive helper function to store Topological
  76.     // Sort starting from all vertices one by one
  77.     for (int i = 0; i < V; i++)
  78.         if (visited[i] == false)
  79.             topologicalSortUtil(i, visited, Stack);
  80.  
  81.     // Print contents of stack
  82.     while (Stack.empty() == false)
  83.     {
  84.         cout << Stack.top() << " ";
  85.         Stack.pop();
  86.     }
  87. }
  88.  
  89. // Driver program to test above functions
  90. int main()
  91. {
  92.     // Create a graph given in the above diagram
  93.     Graph g(8);
  94.     g.addEdge(0,4);
  95.     g.addEdge(4,6);
  96.     g.addEdge(6,7);
  97.     g.addEdge(2,6);
  98.     g.addEdge(2,5);
  99.     g.addEdge(1,6);
  100.     g.addEdge(1,5);
  101.     g.addEdge(3,5);
  102.     g.addEdge(5,7);
  103.  
  104.     cout << "Following is a Topological Sort of the given graph \n";
  105.     g.topologicalSort();
  106.  
  107.     return 0;
  108. }
RAW Paste Data