Program to implement Breadth First Search C++

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.

Depth First Search Program in C++

Program to implement Breadth first search C++ :

#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();
}