ব্রেডথ ফার্স্ট সার্চ (বিএফএস)
(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;
}
This is a typical inquiry that a great many people particularly the individuals who are either new or not acquainted with internet showcasing may inquire.SEO Company Primelis
ReplyDelete