This C++ program displays the breadth first traversal of all nodes present in a graph. A graph is a set of nodes connected by edges.

Here is the source code of the C++ program to display the breadth first method of traversing nodes in a graph along with a display of the start and end time of a visited node. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

`/*`

`* C Program to Traverse a Graph using BFS`

`*/`

`#include <iostream>`

`#include <conio.h>`

using namespace std;

int c = 0, t = 0;

`struct node_info`

`{`

int no;

int st_time;

}*q = NULL, *r = NULL, *x = NULL;

`struct node`

`{`

node_info *pt;

node *next;

}*front = NULL, *rear = NULL, *p = NULL, *np = NULL;

void push(node_info *ptr)

`{`

np = new node;

np->pt = ptr;

np->next = NULL;

if (front == NULL)

`{`

front = rear = np;

rear->next = NULL;

`}`

`else`

`{`

rear->next = np;

rear = np;

rear->next = NULL;

`}`

`}`

node_info *remove()

`{`

if (front == NULL)

`{`

cout<<"empty queue\n";

`}`

`else`

`{`

p = front;

x = p->pt;

front = front->next;

delete(p);

return(x);

`}`

`}`

void bfs(int *v,int am[][7],int i)

`{`

if (c == 0)

`{`

q = new node_info;

q->no = i;

q->st_time = t++;

cout<<"time of visitation for node "<<q->no<<":"<<q->st_time<<"\n\n";

v[i] = 1;

push(q);

`}`

c++;

for (int j = 0; j < 7; j++)

`{`

if (am[i][j] == 0 || (am[i][j] == 1 && v[j] == 1))

continue;

else if (am[i][j] == 1 && v[j] == 0)

`{`

r = new node_info;

r->no = j;

r->st_time = t++;

cout<<"time of visitation for node "<<r->no<<":"<<r->st_time<<"\n\n";

v[j] = 1;

push(r);

`}`

`}`

remove();

if (c <= 6 && front != NULL)

bfs(v, am, remove()->no);

`}`

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];

`}`

`}`

bfs(v, am, 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 time of visitation for node 0:0 time of visitation for node 1:1 time of visitation for node 2:2 time of visitation for node 5:3 time of visitation for node 6:4 time of visitation for node 3:5 time of visitation for node 4:6

**Sanfoundry Global Education & Learning Series – 1000 C++ Programs.**

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