গ্রাফ অ্যালগরিদম গুলোর মধ্যে BFS অ্যালগরিদম অন্যতম ।
দেখে অনেক কঠিন মনে হলেও অ্যালগরিদমটা অনেক সহজ ।
আসুন ধাপে ধাপে নিচের প্রবলেম টা সল্ভ করি ...
চিত্রে আমরা যে গ্রাফ টা দেখতে পাচ্ছি এখানে টোটাল ৮ টা ভার্টেক্স আছে
(A,B,C,D,E,F,G,H)
এখন আমরা A ভার্টেক্স থেকে কাজ শুরু করব কারন alphabetically A সবার আগে
এখন আমরা দেখব A এর সাথে সংযুক্ত ভার্টেক্স কোনগুলা আছে
এখানে B,D,G হল A এর সাথে যুক্ত । তাই এই ভার্টেক্স গুলা আমি Queue এ Enqueue করব
এবার আমরা B ভিজিট করব (কারন Queue এ সবার উপরে B আছে )
এবং B Queue থেকে বাদ যাবে । এখন দেখা যাচ্ছে B এর সাথে A,E,F এই ৩টা ভার্টেক্স যুক্ত আছে কিন্তু A আমরা ভিজিট করে ফেলেছি , তাই এখন Queue তে শুধু E,F যাবে
এখন Queue এ সবার উপরে ডি আছে কিন্তু D এর সাথে যে ভার্টেক্স গুলা যুক্ত আছে A,F আগে ভিজিট করা হয়েছে ,তাই D তে এখন কোন কাজ নাই ,তাই আমরা queue থেকে D বাদ দিলাম ।
একই ঘটনা G,E এর সাথে হবে কারন এদের সাথে যুক্ত আনভিজিটেড
কোন ভার্টেক্স নাই
এখন আমরা F তে মুভ করব । F এর সাথে যুক্ত একমাত্র আনভিজিটেড ভার্টেক্স হল C , So F এর পর আমরা C ভিজিট করব এবং F ,C কে Queue থেকে বাদ দিবো
এরপর বাকি থাকে H . H থেকে ভিজিট করার মত আর কিছু নাই সো H ও Queue থেকে বাদ যাবে এবং আমাদের অ্যালগরিদম সম্পন্ন হবে ।
পরিশেষে আমরা যে ফলাফল টা পাচ্ছি তা হলঃ
A B D G E F C H
কোন সমস্যা হলে কমেন্ট করুন
ধন্যবাদ
