# 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
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;
31. }
32.
33. void Graph::addEdge(int v, int w)
34. {
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.
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);