This C program, using recursion, displays the depth first traversal of nodes in a graph. The start and end times of nodes as and when they are encountered are displayed.
Here is the source code of the C program to display the depth first traversal of a graph. The C program is successfully compiled and run on DevCpp, a C++ compiler. The program output is also shown below.
/*
* C++ Program to Traverse a Graph using DFS
*/
#include <iostream>
#include <conio.h>
using namespace std;
int c = 0;
struct node
{
char data;
int st_time, lv_time;
}*p = NULL, *r = NULL;
struct stack
{
node *pt;
stack *next;
}*top = NULL, *q = NULL, *np= NULL;
void push(node *ptr)
{
np = new stack;
np->pt = ptr;
np->next = NULL;
if (top == NULL)
{
top = np;
}
else
{
np->next = top;
top = np;
}
}
node *pop()
{
if (top == NULL)
{
cout<<"underflow\n";
}
else
{
q = top;
top = top->next;
return(q->pt);
delete(q);
}
}
void create(int a[], int b[][7], int i, int j)
{
c++;
p = new node;
cout<<"enter data for new node\n";
cin>>p->data;
p->st_time = c;
cout<<"start time for "<<p->data<<" is "<<c<<endl;
a[i] = 1;
push(p);
while (j < 7)
{
if ((b[i][j] == 0) || (b[i][j] == 1 && a[j] == 1))
{
j++;
}
else if (b[i][j] == 1 && a[j] == 0)
{
create(a,b,j,0);
}
}
r = pop();
cout<<"node popped\n";
c++;
cout<<"leave time for "<<r->data<<" is "<<c<<endl;
return;
}
int main()
{
int a[7];
for (int i = 0; i < 7; i++)
{
a[i] = 0;
}
int b[7][7];
cout<<"enter values for adjacency matrix"<<endl;
for (int i = 0 ; i < 7 ; i++ )
{
cout<<"enter values for "<<(i+1)<<" row"<<endl;
for (int j = 0; j < 7; j++)
{
cin>>b[i][j];
}
}
create(a,b,0,0);
getch();
}
Output: enter values for adjacency matrix enter values for 1 row 0 1 1 0 0 1 1 enter values for 2 row 1 0 0 0 0 0 0 enter values for 3 row 1 0 0 0 0 0 1 enter values for 4 row 0 0 0 0 1 1 0 enter values for 5 row 0 0 0 1 0 1 1 enter values for 6 row 1 0 0 1 1 0 0 enter values for 7 row 1 0 1 0 1 0 0 enter data for new node a start time for a is 1 enter data for new node b start time for b is 2 node popped leave time for b is 3 enter data for new node c start time for c is 4 enter data for new node d start time for d is 5 enter data for new node e start time for e is 6 enter data for new node f start time for f is 7 enter data for new node g start time for g is 8 node popped leave time for g is 9 node popped leave time for f is 10 node popped leave time for e is 11 node popped leave time for d is 12 node popped leave time for c is 13 node popped leave time for a is 14
Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
Related Posts:
- Practice Computer Science MCQs
- Check C++ Books
- Apply for C++ Internship
- Check Computer Science Books
- Apply for Computer Science Internship