BFS Algorithm in Bangla (ব্রেডথ ফার্স্ট সার্চ বিএফএস)

ব্রেডথ ফার্স্ট সার্চ (বিএফএস) (Breadth First Search [BFS])

ব্রেডথ ফার্স্ট সার্চ (বিএফএস) হল গ্রাফ ট্রাভার্সাল এর একটি পদ্ধতি। গ্রাফ এর সব গুলো নোড ভিজিট করার জন্য আমরা বিএফএস ব্যবহার করতে পারি । বিএফএস এর মূল বিষয় হল লেভেল অনুযায়ী ট্রাভার্স করা । আনডিরেক্টেড গ্রাফ এর ক্ষেত্রে
বিএফএস ব্যবহার করা হয়।



চিত্রের গ্রাফটির সব নোড ভিজিট করব । এক্ষেত্রে নোড এর তিনটি অবস্থা পাওয়া যাবে।
State-1 : নোডগুলো Ready আছে ।
State-2 : নোড Waiting State এ আছে ।
State-3 : নোড Proceed State এ আছে অর্থাৎ Queue থেকে pop হয়েছে ।
একবার এর বেশি নোড ভিজিট হবে না । প্রথমে কিউ Queue নেই একটি




প্রাথমিক অবস্থায় সব নোড এর State=1 হবে ।
এখন A কে Q তে নিয়ে আসব । তাহলে A=2 State এ যাবে ।
এখন A কে Queue থেকে pop করে process করে দিব এবং A এর State=3 হয়ে যাবে ।এখন যতক্ষন Queue empty না হয় A এর Adjacent Node গুলো Queue
তে রাখব । তাহলে কিউ হবে এমন




তাহলে B C E এর State=2 হয়ে যাবে ।
এখন কিউ খালি না হওয়া পর্যন্ত কিউ এর ফ্রন্ট এর থেকে নোড পপ করতে থাকব এবং সেই নোড এর Adjacent Node গুলো কে কিউ এ পুশ করব ।

তাহলে B কে পপ করে প্রসেস করব এবং এরপর B এর Adjacent Node গুলো D, F কে কিউ তে পুশ করব ।




অনূরুপভাবে C কে পপ করব এবং C এর Adjacent Node গুলো কে পুশ করব । যেহেতু C এর সব Adjacent Node আগে থেকেই কিউ এ আছে তাই শুধু পপ করব ।
অনূরুপভাবে D কে পপ করব এবং D এর Adjacent Node গুলো কে পুশ করব । যেহেতু D এর সব Adjacent Node আগে থেকেই কিউ এ আছে তাই শুধু পপ করব ।

একইভাবে F কেও পপ করে ফেলার পর কিউ খালি হয়ে যাবে এবং আমরা বিএফএস ট্রাভার্স সিকুয়েন্স পেয়ে যাব । পপ করে প্রসেস করার ক্রম অনুযায়ী Sequence

              A -> B -> C -> E -> D -> F





BFS Code (C++)

#include <bits/stdc++.h>
using namespace std;
vector<int>edges[100];
queue<int>q;
vector<int>item;
int level[100],parent[100],visited[100],tn;

void bfs(int s)
{
    int j,k,fr;
    q.push(s);
    level[s]=0;
    for(j=0;j<tn;j++)
    {
        visited[j]=0;
    }
    visited[s]=1;
    while(!q.empty())
    {
        fr=q.front();
        for(k=0;k<edges[fr].size();k++)
        {
            if(visited[edges[fr][k]]==0)
            {
                 q.push(edges[fr][k]);
                 level[edges[fr][k]]=level[fr]+1;
                 parent[edges[fr][k]]=fr;
                 visited[edges[fr][k]]=1;
            }


        }
        item.push_back(q.front());
        q.pop();
    }
}


int main()
{
    int i,e,p,n,u,v,f,m;
    cout<<"Enter Total Nodes And Edges="<<endl;
    cin>>tn>>e;
    for(i=1;i<=e;i++)
    {
        cin>>u>>v;
        edges[u].push_back(v);
    }
    cout<<"Enter 1st node"<<endl;
    cin>>f;
    bfs(f);
    cout<<"Enter Node to know shortest path"<<endl;
    cin>>n;
    cout<<"Shortest Path is="<<level[n]<<endl;
    cout<<"Enter Node To Know its Parent"<<endl;
    cin>>p;
    while(p!=f)
    {
        p=parent[p];
    }
    cout<<"Parent is="<<p<<endl;
    cout<<"Sequence="<<endl;
    for(m=0;m<item.size();m++)
    {
        cout<<item[m];
    }
    return 0;
}


Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment