কম্পিউটার

একটি গ্রাফে টপোলজিকাল বাছাই করা যায় কিনা তা পরীক্ষা করার জন্য C++ প্রোগ্রাম


একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফে, আমরা টপোলজিকাল সাজানোর ব্যবহার করে শীর্ষবিন্দুগুলিকে রৈখিক ক্রমে সাজাতে পারি।

টপোলজিক্যাল সর্ট শুধুমাত্র নির্দেশিত অ্যাসাইক্লিক গ্রাফে কাজ করে। একটি ডাইরেক্টেড অ্যাসাইক্লিক গ্রাফে (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

  1. একটি অনির্দেশিত গ্রাফে ইউলারিয়ান পাথ রয়েছে কিনা তা পরীক্ষা করার জন্য C++ প্রোগ্রাম

  2. একটি অনির্দেশিত গ্রাফে ইউলারিয়ান চক্র রয়েছে কিনা তা পরীক্ষা করার জন্য C++ প্রোগ্রাম

  3. একটি নির্দেশিত গ্রাফে ইউলারিয়ান চক্র রয়েছে কিনা তা পরীক্ষা করার জন্য C++ প্রোগ্রাম

  4. একটি গ্রাফ দৃঢ়ভাবে সংযুক্ত কি না তা পরীক্ষা করার জন্য C++ প্রোগ্রাম