Code States # 2 : Breadth First Search Algorithm for Graph

Hello Again!
For those who are not aware of this new series on Code States, in short, here you will get all the relevant codes. It has a two way benefits. I get to keep my codes handy instead of in some misspelled , never to be found folder in some random directory of my system. You get to have the coded implementations of the modules for free. Not everyone wants to do low level coding. They want modules. This will surely help.

See Code States # 1 for Depth First Search Algorithm.

Applications of Breadth First Search:

1. Find the shortest path between two points in a greedy manner in an unweighted graph .
2. To check the number of connected components in a graph.

Some Real world applications:

• GPS Navigation systems: Navigation systems such as the Google Maps, which can give directions to reach from one place to another use BFS. They take your location to be the source node and your destination as the destination node on the graph. (A city can be represented as a graph by taking landmarks as nodes and the roads as the edges that connect the nodes in the graph.) BFS is applied and the shortest route is generated which is used to give directions or real time navigation.
• Computer Networks: Peer to peer (P2P) applications such as the torrent clients need to locate a file that the client (one who wants to download the file) is requesting. This is achieved by applying BFS on the hosts (one who supplies the file) on a network. Your computer is the host and it keeps traversing through the network to find a host for the required file (maybe your favourite movie).
• Facebook: It treats each user profile as a node on the graph and two nodes are said to be connected if they are each other's friends. Infact, apply BFS on the facebook graph and you will find that any two people are connected with each other by atmost five nodes in between. To say, that you can reach any random person in the world by traversing 5 nodes in between. (I did not run BFS on facebook graph, it is a well known fact).What do you think is the new facebook "Graph Search"? (It is not directly BFS, but a lot of modifications over classic graph search algorithms.)
• Web Crawlers: It is quite an interesting application. They can be used to analyze what all sites you can reach by following links randomly on a particular website. 

So have the code and enjoy. See you soon.

Edit ---- The parsing for blogspot is just something i wont appreciate a lot. You can instead find the codes in my github repository. Fork me there, to get the code. The link is just below.
harpribotics.blogspot

# include
# define max_node 50
using namespace std;

struct adjlist{
 int vertex;
 adjlist* next;
};

adjlist *adj[max_node];

int totNodes;

int queue[max_node]; 
int f = -1; // front queue pointer
int r = -1; // rear queue pointer

// to insert in the queue
void q_insert (int item){
 r = r + 1;
 queue[r] = item;
 if(f == -1)
  f = 0;
 
}

// to delete in the queue
int q_delete (){
 int delitem = queue[f];
 if(f == r)
  f = r = -1;
 else
  f = f + 1;
 return(delitem);
}

// to check if the queue is empty
int is_q_empty(){
    if(f==-1)
      return(1);
    else return(0);
}
// creat the adjascency list of the graph

void createGraph(){
 adjlist *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 "< That is Total Neighbours of "<>neighbours;
        for(int j=1;j<=neighbours;j++){
            cout<<"Enter neighbour #"<>neighbour_value;
            newl=new adjlist;
            newl -> vertex = neighbour_value;
            newl -> next = NULL;
            if(adj[i] == NULL){
             adj[i] = newl;
             last = newl;
            }
            else{
             last -> next = newl;
             last = newl;
            }
        }
    }
}

void BFS_traversal(){
    adjlist *tmp;
    int N,v,start_node,status[max_node];//status arr for maintaing status.
 const int 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<<" "<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;
        }
    }
}

int main(){
    
    cout<<"*****Breadth First Search Traversal*****\n";
    createGraph();
    cout<<"\n===BFS traversal is as under===\n";
    BFS_traversal();
    int n;
    cin>>n;
}