Algorithm: BFS(Breadth First Search)

Theory:

http://scanftree.com/Data_Structure/Breadth-First-Search

Bangla:

গ্রাফ থিওরিতে হাতেখড়ি-৪(ব্রেডথ ফার্স্ট সার্চ)

Video:

code implementation:

Some other links may help:

http://theoryofprogramming.com/2014/12/25/breadth-first-search-algorithm/

code:

//bfs implementation for undirected unweighted graph
#include<fstream>
#include<queue>
#include<vector>
#include<iostream>
using namespace std;

int main()
{
    int n,m,start;
    int a,b;
    cin>>n>>m>>start;
    vector<int> samp;
    vector<vector<int> > conn(n+1,samp); //conn taking custom value in vector to make it sizeable

    //loading adjacency matrix
    for(int i=0; i<m; i++)
    {
        cin>>a>>b;
        conn[a].push_back(b);
        conn[b].push_back(a);
    }
    bool visited[n+1]; //visited node 1 to last
    for(int i=0; i<n+1; i++)
    {
        visited[i]=false;  //making each and every node false
    }
    queue<int> Q;  //creating a queue
    Q.push(start); //pushing the starting node in the queue
    visited[start]=true; //make the starting node only true
    int siz=0;
    int lev=0;
    while(!Q.empty())
    {
        cout<<"LEVEL:"<<lev<<endl;
        siz=Q.size();
        while(siz--)
        {
            int first=Q.front();
            Q.pop();
            cout<<first<<endl;
            for(int j=0; j<conn[first].size(); j++)
            {
                if(!visited[conn[first][j]])
                {
                visited[conn[first][j]]=true; //making true which have visited
                Q.push(conn[first][j]); //pushing the value in the queue
                }
            }

        }
        lev++; //level increasing in each iteration
    }
return 0;
}

Input:

9 10 1 //here 1 is starting node that can be any value
1 2
1 3
3 4
3 5
1 6
4 6
4 9
9 8
1 7
7 3

Output:

Another code tried to write from the pseudocode is:

#include<iostream>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
//void BFS(int);
int WHITE=1,GRAY=2,BLACK=3,inf=31000,NIL=-1;
int num_e,num_v;
queue<int> Q;
int adj[20][20],color[20],d[20],p[20];
void initialization()
{
    int k,j;
    for(k=0; k<20; k++)
    {
        for(j=0; j<20; j++)
        {
            adj[k][j]=0;
        }
    }
}
void build_adj_matrix()
{
    int i,a,b;
    cin>>num_v;
    cin>>num_e;
    for(i=1; i<=num_e; i++)
    {
        cin>>a>>b;
        adj[a][b]=1;
        adj[b][a]=1;
    }
}
void BFS(int s)
{
    int i,u,v;
    for(i=1; i<=num_v; i++)
    {
        color[i]=WHITE;
        d[i]=inf;
        p[i]=NIL;
    }
    color[s]=GRAY;
    d[s]=0;
    p[s]=NIL;
    Q.push(s);
    while(!Q.empty())
    {
        int u=Q.pop();
        for(v=1; v<=num_v; v++)
        {
            if(adj[u][v]==1)
            {
                if(color[v]==WHITE)
                {
                    color[v]=GRAY;
                    d[v]=d[u]+1;
                    p[v]=u;
                    Q.push(v);
                }
            }
        }
        color[u]=BLACK;
    }
}
void distance_output()
{
    int i;
    cout<<"Shortest path from source vertex";
    for(i=1; i<=num_v; i++)
    {
        cout<<"to node "<<i<<"is "<<d[i];

    }
}
void path_print(int s,int v)
{
    if(v==s)
    {
        cout<<s<<endl;
    }
    else if(p[v]==NIL)
    {
        cout<<"No path from"<<s<<"to "<<v<<"exists";
    }
    else
    {
        path_print(s,p[v]);
        cout<<v<<endl;
    }
}
int main()
{

    int source,destination;
    initialization();
    build_adj_matrix();
    cin>>source;
    cin>>destination;
    BFS(source);
    distance_output();
    path_print(source,destination);
    return 0;
}

reference from java code: http://www.programmingboss.com/2014/06/breadth-first-search-bfs-in-java.html

ppt slide: https://drive.google.com/file/d/0B0sCkwd_qKgJSzZyUWVYZU5GWlk/edit