C++ Program to Detect Cycle in a Graph using Topological Sort

This C++ program displays the topological sort method of finding whether a given graph contains cycles or not using Kosaraju’s Algorithm.

Here is the source code of the C++ program to display whether the graph given as input contains cycles or not. This C++ program is successfully compiled and run on DevCpp, a C++ compiler.The program output is given below.

  1. /*
  2.  * C++ Program to Check Cycle in a Graph using Topological Sort
  3.  */
  4. #include<iostream>
  5. #include<conio.h>
  6. using namespace std;
  7. struct node_info
  8. {
  9.     int no;
  10.     int lv_time, st_time;
  11. }*q = NULL;
  12. struct node
  13. {
  14.     node_info *pt;
  15.     node *next;
  16. }*top = NULL, *p = NULL, *np = NULL;
  17. struct node1
  18. {
  19.     node1 *link;
  20.     node_info *pt1;
  21. }*head = NULL, *m = NULL, *n = NULL, *np1 = NULL;
  22. int c = 0;
  23. bool flag = false;
  24. void push(node_info *ptr)
  25. {
  26.     np = new node;
  27.     np->pt = ptr;
  28.     np->next = NULL;
  29.     if (top == NULL)
  30.     {
  31.         top = np;
  32.     }
  33.     else
  34.     {
  35.         np->next = top;
  36.         top = np;
  37.     }
  38. }
  39. node_info *pop()
  40. {
  41.     if (top == NULL)
  42.     {
  43.         cout<<"underflow\n";
  44.     }
  45.     else
  46.     {
  47.         p = top;
  48.         top = top->next;
  49.         return(p->pt);
  50.         delete(p);
  51.     }
  52. }
  53. void store(node_info *ptr1)
  54. {
  55.     np1 = new node1;
  56.     np1->pt1 = ptr1;
  57.     np1->link = NULL;
  58.     if (c == 0)
  59.     {
  60.         head = np1;
  61.         m = head;
  62.         m->link = NULL;
  63.         c++;
  64.     }
  65.     else
  66.     {
  67.         m = head;
  68.         np1->link = m;
  69.         head = np1;
  70.     }
  71. }
  72. void remove(int x)
  73. {
  74.     m = head;
  75.     if ((m->pt1)->no == x)
  76.     {
  77.         head = head->link;
  78.         delete(m);
  79.     }
  80.     else
  81.     {
  82.         while ((m->pt1)->no != x && m->link != NULL)
  83.         {
  84.             n = m;
  85.             m = m->link;
  86.         }
  87.         if ((m->pt1)->no == x)
  88.         {
  89.             n->link = m->link;
  90.             delete(m);
  91.         }
  92.         else if (m->link == NULL)
  93.         {
  94.             flag = true;
  95.             cout<<"Cycles do not exist in graph\n";
  96.         }
  97.     }
  98. }            
  99. void topo(int *v, int am[][5], int i)
  100. {
  101.     q = new node_info;
  102.     q->no = i;
  103.     q->st_time = c;
  104.     push(q);
  105.     v[i] = 1;
  106.     for (int j = 0; j < 5; j++)
  107.     {
  108.         if (am[i][j] == 0  || (am[i][j] == 1 && v[j] == 1))
  109.             continue;
  110.         else if(am[i][j] == 1 && v[j] == 0)
  111.         {
  112.             c++;
  113.             topo(v,am,j);
  114.         }
  115.     }
  116.     c++;
  117.     q = pop();
  118.     q->lv_time = c;
  119.     store(q);
  120.     return;
  121. }
  122. void topo1(int *v, int am[][5], int i)
  123. {
  124.     v[i] = 1;
  125.     remove(i);
  126.     for (int j = 0; j < 5; j++)
  127.     {
  128.         if (am[i][j] == 0  || (am[i][j] == 1 && v[j] == 1))
  129.         {
  130.             continue;
  131.         }
  132.         else if(am[i][j] == 1 && v[j] == 0)
  133.         {
  134.             topo1(v, am, j);
  135.         }
  136.     }
  137.     return;
  138. }
  139. void addEdge(int am[][5], int src, int dest)
  140. {
  141.      am[src][dest] = 1;
  142.      return;
  143. }
  144. int main()
  145. {
  146.     int v[5], am[5][5], amt[5][5], c = 0, a, b;
  147.     for (int i = 0; i < 5; i++)
  148.     {
  149.         v[i] = 0;
  150.     }
  151.     for (int i = 0; i < 5; i++)
  152.     {
  153.         for (int j = 0; j < 5; j++)
  154.         {
  155.             am[i][j] = 0;
  156.         }
  157.     }
  158.     while (c < 5)
  159.     {
  160.         cout<<"Enter the source and destination\n";
  161.         cin>>a>>b;
  162.         addEdge(am, a, b);
  163.         c++;
  164.     }
  165.     topo(v, am, 0);
  166.     for (int i = 0; i < 5; i++)
  167.     {
  168.         v[i] = 0;
  169.         for (int j = 0; j < 5; j++)
  170.         {
  171.             amt[j][i] = am[i][j];
  172.         }
  173.     }
  174.     if (head != NULL)
  175.     {                 
  176.         topo1(v, amt, (head->pt1)->no);
  177.         if (flag == false)
  178.         {
  179.             cout<<"Cycles exist in graph\n";
  180.         }
  181.     }
  182.     getch();
  183. }

Output
Enter the source and destination
0
2
Enter the source and destination
0
3
Enter the source and destination
1
0
Enter the source and destination
2
1
Enter the source and destination
3
4
Cycles exist in graph

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.