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.

`/*`

`* C++ Program to Find all Back Edges in a Graph`

`*/`

`#include<iostream>`

`#include<conio.h>`

using namespace std;

`struct node_info`

`{`

int no;

}*q = NULL,*r = NULL;

`struct node`

`{`

node_info *pt;

node *next;

}*top = NULL,*p = NULL,*np = NULL;

void push(node_info *ptr)

`{`

np = new node;

np->pt = ptr;

np->next = NULL;

if (top == NULL)

`{`

top = np;

`}`

`else`

`{`

np->next = top;

top = np;

`}`

`}`

node_info *pop()

`{`

if (top == NULL)

`{`

cout<<"underflow\n";

`}`

`else`

`{`

p = top;

top = top->next;

return(p->pt);

delete(p);

`}`

`}`

void back_edges(int *v,int am[][7],int i,int k)

`{`

cout<<"\n\nDISPLAYING BACK EDGES\n\n";

q = new node_info;

q->no = i;

push(q);

v[i] = 1;

for (int j = 0; j < 7; j++)

`{`

if (am[i][j] == 1 && v[j] == 0)

`{`

c++;

back_edges(v,am,j,i);

`}`

else if (am[i][j] == 0)

continue;

else if ((j == k) && (am[i][k] == 1 && v[j] == 1))

continue;

`else`

`{`

cout<<"Back edge present between "<<i<<" th node and "<<j<<" th node"<<endl;

am[i][j] = 0;

am[j][i] = 0;

continue;

`}`

`}`

r = pop();

return;

`}`

int main()

`{`

int v[7],am[7][7];

for (int i = 0; i < 7; i++)

v[i] = 0;

for (int i = 0; i < 7; i++)

`{`

cout<<"enter the values for adjacency matrix row:"<<i + 1<<endl;

for(int j = 0; j < 7; j++)

`{`

cin>>am[i][j];

`}`

`}`

back_edges(v,am,0,0);

getch();

`}`

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.**

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