ব্রেডথ ফার্স্ট সার্চ (BFS) ট্রাভার্সাল একটি অ্যালগরিদম, যা দিয়ে একটি দেওয়া গ্রাফের সব নোড ভিজিট করা হয়। এই ট্রাভার্সাল অ্যালগরিদমে একটি নোড সিলেক্ট করা হয় এবং তারপর সব আডজাসেন্ট নোড এক-এক করে ভিজিট করা হয়। সব আডজাসেন্ট ভার্টেক্স কমপ্লিট হলে, এটি অন্য একটি ভার্টেক্সে যেতে এবং আবার তার আডজাসেন্ট ভার্টেক্সগুলো চেক করে।
এই অ্যালগরিদম ইমপ্লিমেন্ট করতে হলে, কিউ (Queue) ডেটা স্ট্রাকচার ব্যবহার করতে হয়। সব আডজাসেন্ট ভার্টেক্স কিউ-তে অ্যাড করা হয়, সব আডজাসেন্ট ভার্টেক্স কমপ্লিট হলে, কিউ থেকে একটি আইটেম রিমুভ করে সেটি থেকে আবার ট্রাভার্স শুরু করা হয়।
গ্রাফে কখনো সাইকেল থাকতে পারে, তাই একটি অ্যারে ব্যবহার করা হয় নোডটি ইতিমধ্যে ভিজিটেড হয়েছে কিনা তা মার্ক করার জন্য।
ইনপুট এবং আউটপুট
ইনপুট: গ্রাফের এডজেসেন্সি ম্যাট্রিক্স। 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)
ইনপুট - ভার্টেক্সের লিস্ট, এবং শুরুর ভার্টেক্স।
আউটপুট - গ্রাফ কানেক্টেড থাকলে সব নোড ট্রাভার্স করা।
শুরু
একটি খালি কিউ que ডিফাইন করুন
প্রথমে সব নোডের স্ট্যাটস আনভিজিটেড হিসেবে মার্ক করুন
start ভার্টেক্স কিউ-তে অ্যাড করুন
যতক্ষণ que খালি নয়, করুন
que থেকে আইটেম ডিলিট করুন এবং u-তে সেট করুন
ভার্টেক্স u ডিসপ্লে করুন
u-এর সাথে আডজাসেন্ট সব ভার্টেক্স i-এর জন্য করুন
যদি vertices[i] আনভিজিটেড হয়, তবে
vertices[i] কে টেম্পোরারিলি ভিজিটেড মার্ক করুন
v কে কিউ-তে অ্যাড করুন
মার্ক করুন
শেষ
u কে কমপ্লিটলি ভিজিটেড মার্ক করুন
শেষ
শেষ
উদাহরণ
#include<iostream> #include<queue> #define NODE 6 using namespace std; typedef struct node { int val; int state; //স্ট্যাটাস }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<node> que; for(i = 0; i
আউটপুট
BFS Traversal: B A D E C F
