### What is Breadth First Search?

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph) and explores the neighbor nodes first, before moving to the next level neighbors. Compare BFS with the equivalent, but more memory-efficient iterative deepening depth-first search and contrast with depth-first search.

For example, in the above graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we donâ€™t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. Breadth First Traversal of the following graph is 2, 0, 3, 1.

### Following is the Program to implement Breadth first search C++ with explanation.

### PROGRAM:

#include <iostream.h> #include <conio.h> #define MAX_NODE 50 struct node{ int vertex; node *next; }; node *adj[MAX_NODE]; //For storing Adjacency list of nodes.int totNodes; //No. of Nodes in Graph.////////////Queue Operation\\\int queue[MAX_NODE],f=-1,r=-1; void q_insert(int item){ r = r+1; queue[r]=item; if(f==-1) f=0; } int q_delete(){ int delitem=queue[f]; if(f==r) f=r=-1; else f=f+1; return(delitem); } int is_q_empty(){ if(f==-1) return(1); elsereturn(0); } ////////////Queue Operation\\\void createGraph(){ node *newl,*last; int neighbours,neighbour_value; cout<<"nn---Graph Creation---nn"; cout<<"Enter total nodes in graph : "; cin>>totNodes; for(int i=1;i<=totNodes;i++){ last=NULL; cout<<"nEnter no. of nodes in the adjacency list of node "<<i<<"n"; cout<<"--> That is Total Neighbours of "<<i<<" : "; cin>>neighbours; for(int j=1;j<=neighbours;j++){ cout<<"Enter neighbour #"<<j<<" : "; cin>>neighbour_value; newl=new node; newl->vertex=neighbour_value; newl->next=NULL; if(adj[i]==NULL) adj[i]=last=newl; else{ last->next = newl; last = newl; } } } } void BFS_traversal(){ node *tmp; int N,v,start_node,status[MAX_NODE];//status arr for maintaing status.constint ready=1,wait=2,processed=3; //status of node. cout<<"Enter starting node : "; cin>>start_node; //step 1 : Initialize all nodes to ready state.for(int i=1;i<=totNodes;i++) status[i]=ready; //step 2 : put the start node in queue and change status. q_insert(start_node); //Put starting node into queue. status[start_node]=wait; //change it status to wait state.//step 3 : Repeat until queue is empty.while(is_q_empty()!=1){ //step 4 : Remove the front node N of queue.//process N and change the status of N to//be processed state. N = q_delete(); //remove front node of queue. status[N]=processed; //status of N to processed. cout<<" "<<N; //displaying processed node.//step 5 : Add to rear of queue all the neighbours of N,//that are in ready state and change their status to//wait state. tmp = adj[N]; //for status updation.while(tmp!=NULL){ v = tmp->vertex; if(status[v]==ready){//check status of N's neighbour. q_insert(v); //insert N's neighbour who are in ready state. status[v]=wait; //and make their status to wait state. } tmp=tmp->next; } } } void main(){ clrscr(); cout<<"*****Breadth First Search Traversal*****n"; createGraph(); cout<<"n===BFS traversal is as under===n"; BFS_traversal(); getch(); }