C++ Program to Traverse a Graph using DFS

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.

  1. /*
  2.  * C++ Program to Traverse a Graph using DFS
  3.  */
  4. #include <iostream>
  5. #include <conio.h>
  6. using namespace std;
  7. int c = 0;
  8. struct node
  9. {
  10.     char data;
  11.     int st_time, lv_time;
  12. }*p = NULL, *r = NULL;
  13. struct stack
  14. {
  15.     node *pt;
  16.     stack *next;
  17. }*top = NULL, *q = NULL, *np= NULL;
  18. void push(node *ptr)
  19. {
  20.     np = new stack;
  21.     np->pt = ptr;
  22.     np->next = NULL;
  23.     if (top == NULL)
  24.     {
  25.         top = np;
  26.     }
  27.     else
  28.     {
  29.         np->next = top;
  30.         top = np;
  31.     }
  32. }
  33. node *pop()
  34. {
  35.     if (top == NULL)
  36.     {
  37.         cout<<"underflow\n";
  38.     }
  39.     else
  40.     {
  41.         q = top;
  42.         top = top->next;
  43.         return(q->pt);
  44.         delete(q);
  45.     }
  46. }
  47. void create(int a[], int b[][7], int i, int j)
  48. {
  49.     c++;
  50.     p = new node;
  51.     cout<<"enter data for new node\n";
  52.     cin>>p->data;
  53.     p->st_time = c;
  54.     cout<<"start time for "<<p->data<<" is "<<c<<endl;
  55.     a[i] = 1;
  56.     push(p);
  57.     while (j < 7)
  58.     {
  59.         if ((b[i][j] == 0) || (b[i][j] == 1 && a[j] == 1))
  60.         {
  61.             j++;
  62.         }
  63.         else if (b[i][j] == 1 && a[j] == 0)
  64.         {       
  65.             create(a,b,j,0);
  66.         }
  67.     }
  68.     r = pop();
  69.     cout<<"node popped\n";
  70.     c++;
  71.     cout<<"leave time for "<<r->data<<" is "<<c<<endl;
  72.     return;
  73. }
  74. int main()
  75. {
  76.     int a[7];
  77.     for (int i = 0; i < 7; i++)
  78.     {
  79.         a[i] = 0;
  80.     }
  81.     int b[7][7];
  82.     cout<<"enter values for adjacency matrix"<<endl;
  83.     for (int i = 0 ; i < 7 ; i++ )
  84.     {
  85.         cout<<"enter values for "<<(i+1)<<" row"<<endl;
  86.         for (int j = 0; j < 7; j++)
  87.         {
  88.             cin>>b[i][j];
  89.         }
  90.     }
  91.     create(a,b,0,0);
  92.     getch();
  93. }

 
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.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.