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

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

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!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter