सी ++ प्रोग्राम यह जांचने के लिए कि क्या ग्राफ में टोपोलॉजिकल सॉर्टिंग की जा सकती है

डायरेक्टेड एसाइक्लिक ग्राफ़ में, हम टोपोलॉजिकल सॉर्ट का उपयोग करके वर्टिस को रैखिक क्रम में सॉर्ट कर सकते हैं।

टोपोलॉजिकल सॉर्ट केवल डायरेक्टेड एसाइक्लिक ग्राफ पर काम करता है। डायरेक्टेड एसाइक्लिक ग्राफ (DAG) में, एक से अधिक टोपोलॉजिकल सॉर्ट हो सकते हैं।

निम्नलिखित C++ प्रोग्राम में, हम ग्राफ में एक चक्र के अस्तित्व की जांच करने के लिए टोपोलॉजिकल सॉर्ट करेंगे।

एल्गोरिदम

कार्य के लिए Topo_Sort

Begin
   Define function Topo_Sort()
      Declare x to the integer datatype, vstd[] of the Boolean array and Stack as a stack.
         Pass them as parameter.
      Initialize vstd[x] = true to mark the current node as vstd.
      Declare an iterator i.
      for (i = a[x].begin(); i != a[x].end(); ++i)
         if (!vstd[*i]) then
      Call Topo_Sort(*i, vstd, Stack) function.
   Call push() function to insert values into stack.
End.

उदाहरण

#include<iostream>
#include <list>
#include <stack>
using namespace std;
class grph { // Class to represent a graph
   int ver;
   list<int> *a; // Pointer to an array containing adjacency listsList
   void Topo_Sort(int x, bool vstd[], stack<int> &Stack); // A function used by TopologicalSort
   public:
      grph(int ver); // Constructor of grpf
   void Insert_Edge(int x, int y); // to insert an edge to graph
   void Topol_Sort(); // prints a Topological Sort of the complete graph
};
grph::grph(int ver) {
   this->ver = ver;
   a = new list<int>[ver];
}
void grph::Insert_Edge(int x, int y) {
   a[x].push_back(y); // Add y to x’s list.
}
// A recursive function used by Topol_Sort
void grph::Topo_Sort(int x, bool vstd[], stack<int> &Stack) {
   vstd[x] = true; // Mark the current node as vstd.
   list<int>::iterator i;
   for (i = a[x].begin(); i != a[x].end(); ++i)
      if (!vstd[*i])
         Topo_Sort(*i, vstd, Stack);
   // Push current vertex to stack which stores result
   Stack.push(x);
}
void grph::Topol_Sort() {
   stack<int> Stack;
   // Mark all the vertices as not vstd
   bool *vstd = new bool[ver];
   for (int i = 0; i < ver; i++)
      vstd[i] = false;
   for (int i = 0; i < ver; i++)
      if (vstd[i] == false)
         Topo_Sort(i, vstd, Stack);
   while (Stack.empty() == false) {
      cout << Stack.top() << " ";
      Stack.pop();
   }
}
int main() {
   grph g(6); // Create a graph given in the above diagram
   g.Insert_Edge(5, 2);
   g.Insert_Edge(5, 0);
   g.Insert_Edge(4, 0);
   g.Insert_Edge(4, 1);
   g.Insert_Edge(2, 3);
   g.Insert_Edge(3, 1);
   cout << "Topological Sort of the graph is: \n";
   g.Topol_Sort();
   return 0;
}

आउटपुट

Topological Sort of the graph is:
5 4 2 3 1 0