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

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

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

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

उदाहरण के लिए

एल्गोरिदम

Topological Sort:
Begin
   Declare topo_sort(int *v, int T_S[][5], int i) function
      a = new NodeInfo.
      a->n = i
      a->S_Time = cn.
      Call push_node(a) function to insert data.
      v[i] = 1.
      for (int j = 0; j < 5; j++)
         if (T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1)) then
            continue.
         else if(T_S[i][j] == 1 && v[j] == 0) then
            cn++.
            Call topo_sort(v,T_S, j) function.
      cn++.
      a = pop().
      a->L_Time = cn.
      Store_Node(a).
End.

उदाहरण

#include<iostream>
#include<conio.h>
using namespace std;
struct NodeInfo {
   int n;
   int L_Time, S_Time;
}
*a = NULL;
struct Node {
   NodeInfo *ptr;
   Node *nxt;
}
*t = NULL, *b = NULL, *npt = NULL;
struct Node_Link {
   Node_Link *lk;
   NodeInfo *ptr1;
}
*hd = NULL, *m = NULL, *n = NULL, *npt1 = NULL;
int cn = 0;
bool flag = false;
void push_node(NodeInfo *pt) { //insert data
   npt = new Node;
   npt->ptr = pt;
   npt->nxt = NULL;
   if (t == NULL) {
      t = npt;
   } else {
      npt->nxt = t;
      t = npt;
   }
}
NodeInfo *pop() {
   if (t == NULL) {
      cout<<"underflow\n";
   } else {
      b = t;
      t = t->nxt;
      return(b->ptr);
      delete(b);
   }
}
void Store_Node(NodeInfo *pt1) { //store data
   npt1 = new Node_Link;
   npt1->ptr1 = pt1;
   npt1->lk = NULL;
   if (cn == 0) {
      hd = npt1;
      m = hd;
      m->lk = NULL;
      cn++;
   } else {
      m = hd;
      npt1->lk = m;
      hd = npt1;
   }
}
void delete_node(int x) { //delete node
   m = hd;
   if ((m->ptr1)->n == x) {
      hd = hd->lk;
      delete(m);
   } else {
      while ((m->ptr1)->n != x && m->lk != NULL) {
         n = m;
         m = m->lk;
      }
      if ((m->ptr1)->n == x) {
         n->lk = m->lk;
         delete(m);
      } else if (m->lk == NULL) {
         flag = true;
         cout<<"There is no circle in this graph\n";
      }
   }
}
void topo_sort(int *v, int T_S[][5], int i) { //performing topological sort
   a = new NodeInfo;
   a->n = i;
   a->S_Time = cn;
   push_node(a);
   v[i] = 1;
   for (int j = 0; j < 5; j++) {
      if (T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1))
         continue;
      else if(T_S[i][j] == 1 && v[j] == 0) {
         cn++;
         topo_sort(v,T_S,j);
      }
   }
   cn++;
   a = pop();
   a->L_Time = cn;
   Store_Node(a);
   return;
}
void topologic_sort(int *v, int T_S[][5], int i) {
   v[i] = 1;
   delete_node(i);
   for (int j = 0; j < 5; j++) {
      if (T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1)) {
         continue;
      } else if(T_S[i][j] == 1 && v[j] == 0) {
         topologic_sort(v, T_S, j);
      }
   }
   return;
}
void Insert_Edge(int T_S[][5], int source, int destination) { // insert the value of edge.
   T_S[source][destination] = 1;
   return;
}
int main() {
   int v[5], T_S[5][5], T_S_N[5][5], cn = 0, a, b;
   for (int i = 0; i < 5; i++) {
      v[i] = 0;
   }
   for (int i = 0; i < 5; i++) {
      for (int j = 0; j < 5; j++) {
         T_S[i][j] = 0;
      }
   }
   while (cn < 5) {
      cout<<"Enter the source: ";
      cin>>a;
      cout<<"Enter the destination: ";
      cin>>b;
      cout<<endl;
      Insert_Edge(T_S, a, b);
      cn++;
   }
   topo_sort(v, T_S, 0);
   for (int i = 0; i < 5; i++) {
      v[i] = 0;
      for (int j = 0; j < 5; j++) {
         T_S_N[j][i] = T_S[i][j];
      }
   }
   if (hd != NULL) {
      topologic_sort(v, T_S_N, (hd->ptr1)->n);
      if (flag == false) {
         cout<<"There is a cycle in this graph...\n";
      }
   }
   getch();
}

आउटपुट

Enter the source: 0
Enter the destination: 1

Enter the source: 1
Enter the destination: 2

Enter the source: 2
Enter the destination: 3

Enter the source: 3
Enter the destination: 4

Enter the source: 4
Enter the destination: 0

There is a cycle in this graph...