图的拓扑排序代码

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