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

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