ব্রেডথ ফার্স্ট সার্চ (BFS) ট্রাভার্সাল একটি অ্যালগরিদম যা একটি দেওয়া গ্রাফের সব নোড ভিজিট করতে ব্যবহৃত হয়। এই ট্রাভার্সাল অ্যালগরিদমে একটি নোড সিলেক্ট করা হয় এবং তারপর সব এডজেসেন্ট নোড একে পর একে ভিজিট করা হয়। সব এডজেসেন্ট ভার্টেক্স সম্পন্ন হলে, এটি আরেকটি ভার্টেক্স চেক করতে आगे বড়ে এবং সেটির এডজেসেন্ট ভার্টেক্সগুলো আবার চেক করে।
কম্পিটিটিভ কোডিং-এ, আমাদের সমস্যা খুব দ্রুত সমাধান করতে হয়। আমরা STL (C++-এর স্ট্যান্ডার্ড লাইব্রেরি) ব্যবহার করে এই অ্যালগরিদম বাস্তবায়ন করব, এর জন্য কিউ ডেটা স্ট্রাকচার ব্যবহার করতে হবে। সব এডজেসেন্ট ভার্টেক্স কিউতে যোগ করা হয়, যখন সব এডজেসেন্ট ভার্টেক্স সম্পন্ন হয়, কিউ থেকে একটি আইটেম রিমুভ করা হয় এবং সেই ভার্টেক্স থেকে আবার ট্রাভার্সাল শুরু হয়।
গ্রাফে কখনো কখনো সাইকেল পাওয়া যায়, তাই আমরা একটি অ্যারে ব্যবহার করব নোডটি ইতিমধ্যে ভিজিটেড কিনা চেক করার জন্য।
ইনপুট: গ্রাফের এডজেসেন্সি ম্যাট্রিক্স। 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 Traversal: 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 1 adjacent with u, do
if vertices[i] is unvisited, then
mark vertices[i] as temporarily visited
add v into the queue
end if
done
mark u as completely visited
done
End
উদাহরণ
#include<iostream>
#include<queue>
#define NODE 6
using namespace std;
class node {
public:
int val;
int state; // স্ট্যাটাস
};
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<node> que;
for(i = 0; i < NODE; i++) {
vert[i].state = 0; // নন-ভিজিটেড
}
vert[s.val].state = 1; // ভিজিটেড
que.push(s); // স্টার্টিং নোড ইনসার্ট
while(!que.empty()) {
u = que.front(); // কিউ থেকে ডিলিট এবং প্রিন্ট
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; // নোড u জন্য কমপ্লিটেড
}
}
int main() {
node vertices[NODE];
node start;
char s;
for(int i = 0; i < NODE; i++) {
vertices[i].val = i;
}
s = 'B'; // স্টার্টিং ভার্টেক্স B
start.val = s-'A';
cout << "BFS Traversal: ";
bfs(vertices, start);
cout << endl;
}
আউটপুট
BFS Traversal: B A D E C F
