Logo 
Search:

C++ Programming Articles

Submit Article
Home » Articles » C++ Programming » Data File StructureRSS Feeds

Program of Breadth First Search Traversal ( BFS )

Posted By: Easy Tutor     Category: C++ Programming     Views: 33563

Write a program of Breadth First Search Traversal ( BFS )

Code for Program of Breadth First Search Traversal ( BFS ) in C++ Programming

#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<<"\n\n---Graph Creation---\n\n";
    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();
}
  
Share: 


Didn't find what you were looking for? Find more on Program of Breadth First Search Traversal ( BFS ) Or get search suggestion and latest updates.

Easy Tutor
Easy Tutor author of Program of Breadth First Search Traversal ( BFS ) is from United States. Easy Tutor says

Hello Friends,

I am Free Lance Tutor, who helped student in completing their homework.

I have 4 Years of hands on experience on helping student in completing their homework. I also guide them in doing their final year projects.

I have share many programs on this website for everyone to use freely, if you need further assistance, than please contact me on easytutor.2ya [at the rate] gmail [dot] com

I have special discount scheme for providing tutor services. I am providing tutor service to students from various contries, currently most of my students are from United States, India, Australia, Pakistan, Germany, UK and Canada.

I am also here to expand my technical network to receive more opportunity in my career, make friends to help them in resolving their technical problem, learn and share my knowledge, If you like to be my friend, Please send me friend request.

Thanks,
Happy Programming :)

 
View All Articles

 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
Asif Raza from United States Comment on: Oct 08
hy army... if this program is an error, have a look at the following code
I am sure it will not disappoint you.
in.docsity.com/.../Breadth-first_Search_Algorithm_-_C_plus_plus_Code

Army Ratchaneewan from Thailand Comment on: Sep 09
This Program is Errer
What happen

View All Comments