ব্রেডথ ফার্স্ট সার্চ (BFS) ট্রাভার্সাল একটি অ্যালগরিদম, যা একটি দেয়া গ্রাফের সকল নোড ভিজিট করতে ব্যবহৃত হয়। এই ট্রাভার্সাল অ্যালগরিদমে একটি নোড সিলেক্ট করা হয় এবং তারপর সকল অ্যাডজেসেন্ট নোড একে একে ভিজিট করা হয়। সকল অ্যাডজেসেন্ট ভার্টেক্স কম্প্লিট হলে, এটি আরও ভের্টেক্স চেক করতে চলে যায় এবং সেটার অ্যাডজেসেন্ট ভার্টেক্স আবার চেক করে।
এই অ্যালগরিদম ইমপ্লিমেন্ট করতে, আমাদের কিউ ডেটা স্ট্রাকচার ব্যবহার করতে হবে। সকল অ্যাডজেসেন্ট ভার্টেক্স কিউতে অ্যাড করা হয়, যখন সকল অ্যাডজেসেন্ট ভার্টেক্স কম্প্লিট হয়, তখন কিউ থেকে একটি আইটেম রিমুভ করা হয় এবং সেই ভার্টেক্স থেকে আবার ট্রাভার্সাল শুরু হয়।
গ্রাফে কখনও কখনও সাইকেল থাকতে পারে, তাই আমরা একটি অ্যারে ব্যবহার করব নোডটি ইতিমধ্যে ভিজিটেড কিনা তা মার্ক করার জন্য।
ইনপুট - গ্রাফের অ্যাডজেসেন্সি ম্যাট্রিক্স।
A B C D E F A 0 1 1 1 0 0 B 1 0 0 1 1 0 C 1 0 0 1 0 1 D 1 1 1 0 1 1 E 0 1 0 1 0 1 F 0 0 1 1 1 0
আউটপুট - BFS ট্রাভার্সাল: B A D E C F
অ্যালগরিদম
bfs(vertices, start)
ইনপুট − ভার্টেক্সের লিস্ট, এবং স্টার্ট ভার্টেক্স।
আউটপুট − যদি গ্রাফ কানেক্টেড থাকে, তবে সকল নোড ট্রাভার্স করুন।
Begin
define an empty queue que
at first mark all nodes status as unvisited
add the start vertex into the que
while que is not empty, do
delete item from que and set to u
display the vertex u
for all vertices i adjacent with u, do
if vertices[i] is unvisited, then
mark vertices[i] as temporarily visited
add v into the queue
done
mark u as completely visited
done
End
উদাহরণ (C++)
#include#include #define NODE 6 using namespace std; typedef struct node{ int val; int state; //status }node; int graph[NODE][NODE] = { {0, 1, 1, 1, 0, 0}, {1, 0, 0, 1, 1, 0}, {1, 0, 0, 1, 0, 1}, {1, 1, 1, 0, 1, 1}, {0, 1, 0, 1, 0, 1}, {0, 0, 1, 1, 1, 0} }; void bfs(node *vert, node s){ node u; int i, j; queue que; for(i = 0; i < NODE; i++){ vert[i].state = 0; //not visited } vert[s.val].state = 1;//visited que.push(s); //insert starting node while(!que.empty()){ u = que.front(); //delete from queue and print que.pop(); cout << char(u.val+'A') << " "; for(i = 0; i < NODE; i++){ if(graph[i][u.val]){ if(vert[i].state == 0){ vert[i].state = 1; que.push(vert[i]); } } } u.state = 2;//completed for node u } } int main(){ node vertices[NODE]; node start; char s; for(int i = 0; i < NODE; i++){ vertices[i].val = i; } s = 'B';//starting vertex B start.val = s-'A'; cout << "BFS Traversal: "; bfs(vertices, start); cout << endl; }
আউটপুট
BFS Traversal: B A D E C F
