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

«
»
This C++ program, using recursion, to display the number of back edges in a graph. A back edge is one in which a node points to one of it’s ancestors.

Here is the source code of the C++ program to display the back 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 Back 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. }*q = NULL,*r = NULL;
  11. struct node
  12. {
  13.     node_info *pt;
  14.     node *next;
  15. }*top = NULL,*p = NULL,*np = NULL;
  16. void push(node_info *ptr)
  17. {
  18.     np = new node;
  19.     np->pt = ptr;
  20.     np->next = NULL;
  21.     if (top == NULL)
  22.     {
  23.         top = np;
  24.     }
  25.     else
  26.     {
  27.         np->next = top;
  28.         top = np;
  29.     }
  30. }
  31. node_info *pop()
  32. {
  33.     if (top == NULL)
  34.     {
  35.         cout<<"underflow\n";
  36.     }
  37.     else
  38.     {
  39.         p = top;
  40.         top = top->next;
  41.         return(p->pt);
  42.         delete(p);
  43.     }
  44. }
  45. void back_edges(int *v,int am[][7],int i,int k)
  46. {
  47.      cout<<"\n\nDISPLAYING BACK EDGES\n\n";
  48.      q = new node_info;
  49.      q->no = i;
  50.      push(q);
  51.      v[i] = 1;
  52.      for (int j = 0; j < 7; j++)
  53.      {
  54.          if (am[i][j] == 1 && v[j] == 0)
  55.          {
  56.              c++;
  57.              back_edges(v,am,j,i);
  58.          }
  59.          else if (am[i][j] == 0)
  60.               continue;
  61.          else if ((j == k) && (am[i][k] == 1 && v[j] == 1))
  62.               continue;
  63.          else
  64.          {
  65.              cout<<"Back edge present between "<<i<<" th node and "<<j<<" th node"<<endl;
  66.              am[i][j] = 0;
  67.              am[j][i] = 0;
  68.              continue;
  69.          }
  70.      }
  71.      r = pop();
  72.      return;
  73. }     
  74. int main()
  75. {
  76.     int v[7],am[7][7];
  77.     for (int i = 0; i < 7; i++)
  78.         v[i] = 0;
  79.     for (int i = 0; i < 7; i++)
  80.     {
  81.         cout<<"enter the values for adjacency matrix row:"<<i + 1<<endl;
  82.         for(int j = 0; j < 7; j++)
  83.         {
  84.             cin>>am[i][j];
  85.         }
  86.     }
  87.     back_edges(v,am,0,0);
  88.     getch();
  89. }

advertisement
Output
enter the values for adjacency matrix row:1
0
1
1
0
0
1
1
enter the values for adjacency matrix row:2
1
0
0
0
0
0
0
enter the values for adjacency matrix row:3
1
0
0
0
0
0
1
enter the values for adjacency matrix row:4
0
0
0
0
1
1
0
enter the values for adjacency matrix row:5
0
0
0
1
0
1
1
enter the values for adjacency matrix row:6
1
0
0
1
1
0
0
enter the values for adjacency matrix row:7
1
0
1
0
1
0
0
 
 
DISPLAYING BACK EDGES
 
Back edge present between 6 th node and 0 th node
Back edge present between 5 th node and 0 th node
Back edge present between 5 th node and 4 th node

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

Note: Join free Sanfoundry classes at Telegram or Youtube
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.