C++ Program to Find All Cross Edges in a Graph

«
»
This C++ program, using recursion, displays the number of cross edges in a graph. A cross edge is one in which a node points to another node which has already been fully visited.

Here is the source code of the C++ program to display the cross edges as and when they are encountered. The C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is also shown below.

  1. /*
  2.  * C++ Program to Find all Cross Edges in a Graph
  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, *r = 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. void push(node_info *ptr)
  24. {
  25.     np = new node;
  26.     np->pt = ptr;
  27.     np->next = NULL;
  28.     if (top == NULL)
  29.     {
  30.         top = np;
  31.     }
  32.     else
  33.     {
  34.         np->next = top;
  35.         top = np;
  36.     }
  37. }
  38. node_info *pop()
  39. {
  40.     if (top == NULL)
  41.     {
  42.         cout<<"underflow\n";
  43.     }
  44.     else
  45.     {
  46.         p = top;
  47.         top = top->next;
  48.         return(p->pt);
  49.         delete(p);
  50.     }
  51. }
  52. void store(node_info *ptr1)
  53. {
  54.     np1 = new node1;
  55.     np1->pt1 = ptr1;
  56.     np1->link = NULL;
  57.     if (c == 0)
  58.     {
  59.         head = np1;
  60.         m = head;
  61.         m->link = NULL;
  62.         c++;
  63.     }
  64.     else
  65.     {
  66.         m = head;
  67.         np1->link = m;
  68.         head = np1;
  69.     }
  70. }
  71. int search(int j)
  72. {
  73.     node1 *t = head;
  74.     while (t != NULL)
  75.     {
  76.         if ((t->pt1)->no == j)
  77.         {
  78.             break;
  79.         }
  80.         else
  81.         {
  82.             t = t->link;
  83.             continue;
  84.         }
  85.     }
  86.     return (t->pt1)->lv_time;
  87. }             
  88. int present_in_stack(int j)
  89. {
  90.     int flag = 0;
  91.     p = top;
  92.     while (p != NULL)
  93.     {
  94.         if ((p->pt)->no == j)
  95.         {
  96.             flag = 1;
  97.             return flag;
  98.         }
  99.         p = p->next;
  100.     }
  101.     return flag;
  102. }
  103. void topo(int *v,int am[][8],int i)
  104. {
  105.     q = new node_info;
  106.     q->no = i;
  107.     q->st_time = c;
  108.     push(q);
  109.     v[i] = 1;
  110.     for (int j = 0; j < 8; j++)
  111.     {
  112.         if (am[i][j] == 0)
  113.             continue;
  114.         else if ((am[i][j] == 1 && v[j] == 1))
  115.         {
  116.             if (!present_in_stack(j) && q->st_time > search(j))
  117.             {
  118.                 cout<<"Cross edge between "<<i<<" and "<<j<<endl;
  119.             }
  120.             continue;
  121.         }
  122.         else if(am[i][j] == 1 && v[j] == 0)
  123.         {
  124.             c++;
  125.             topo(v,am,j);
  126.         }
  127.     }
  128.     c++;
  129.     q = pop();
  130.     q->lv_time = c;
  131.     store(q);
  132.     return;
  133. }
  134. int main()
  135. {
  136.     int v[8], am[8][8];
  137.     for (int i = 0; i < 8; i++)
  138.         v[i] = 0;
  139.     for (int i = 0; i < 8; i++)
  140.     {
  141.         cout<<"enter the values for adjacency matrix row:"<<i + 1<<endl;
  142.         for(int j = 0; j < 8; j++)
  143.         {
  144.             cin>>am[i][j];
  145.         }
  146.     }
  147.     topo(v,am,0);
  148.     getch();
  149. }

advertisement
Output
 
enter the values for adjacency matrix row:1
0
1
0
0
1
0
0
1
enter the values for adjacency matrix row:2
0
0
1
0
0
0
0
0
enter the values for adjacency matrix row:3
0
0
0
1
0
0
00
0
enter the values for adjacency matrix row:4
0
1
0
0
0
0
0
0
enter the values for adjacency matrix row:5
0
0
0
0
0
1
0
0
enter the values for adjacency matrix row:6
0
0
1
0
0
0
1
1
enter the values for adjacency matrix row:7
 
0
0
0
0
0
0
0
0
enter the values for adjacency matrix row:8
0
0
0
0
0
0
0
0
Cross edge between 5 and 2

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

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

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 & technical discussions at Telegram SanfoundryClasses.