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.

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

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!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter