একটি গ্রাফের জন্য ব্রেডথ ফার্স্ট সার্চ বা BFS

ব্রেডথ ফার্স্ট সার্চ (BFS) ট্রাভার্সাল হল একটি অ্যালগরিদম, যা একটি প্রদত্ত গ্রাফের সমস্ত নোড দেখার জন্য ব্যবহৃত হয়। এই ট্রাভার্সাল অ্যালগরিদমে একটি নোড নির্বাচন করা হয় এবং তারপরে পার্শ্ববর্তী সমস্ত নোডগুলি একে একে পরিদর্শন করা হয়। সমস্ত সংলগ্ন শীর্ষবিন্দুগুলি সম্পূর্ণ করার পরে, এটি অন্য শীর্ষবিন্দুগুলি পরীক্ষা করার জন্য আরও এগিয়ে যায় এবং এর সন্নিহিত শীর্ষগুলি আবার পরীক্ষা করে৷

এই অ্যালগরিদম বাস্তবায়ন করতে, আমাদের সারি ডেটা কাঠামো ব্যবহার করতে হবে। সমস্ত সংলগ্ন শীর্ষবিন্দুগুলি সারিতে যোগ করা হয়, যখন সমস্ত সন্নিহিত শীর্ষবিন্দু সম্পূর্ণ হয়ে যায়, তখন একটি আইটেম সারি থেকে সরানো হয় এবং আবার সেই শীর্ষবিন্দুর মধ্য দিয়ে যেতে শুরু করে৷

গ্রাফে কখনও কখনও, আমরা কিছু চক্র পেতে পারি, তাই আমরা একটি অ্যারে ব্যবহার করব যখন একটি নোড ইতিমধ্যেই পরিদর্শন করা হয়েছে বা না হয়েছে তা চিহ্নিত করতে৷

ইনপুট - গ্রাফের সংলগ্ন ম্যাট্রিক্স।

A B C D E FA 0 1 1 1 0 0B 1 0 0 1 1 0C 1 0 0 1 0 1D 1 1 0 1 1E 0 1 0 1 0 1F 0 0 1 1 0 

আউটপুট - BFS ট্রাভার্সাল:B A D E C F

অ্যালগরিদম

bfs(শীর্ষ, শুরু)

ইনপুট − শীর্ষবিন্দুর তালিকা, এবং শুরু শীর্ষবিন্দু৷

আউটপুট − সমস্ত নোড অতিক্রম করুন, যদি গ্রাফটি সংযুক্ত থাকে।

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