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.

```
/*
```

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

« Prev - C++ Program to Find All Cross Edges in a Graph

» Next - C++ Program to Find Inverse of a Graph Matrix

Related Posts:

Recommended Articles: