মডিউল ২_১ঃ বিএফএস এলগোরিদম

ধরুন নিচের গ্রাফটি দেওয়া আছেঃ

এই গ্রাফে ০ থেকে ৪ অব্দি ৫টি নোড রয়েছে। আমরা পূর্ববর্তী মডিউলে অ্যাডজেসেন্সি লিস্ট সম্পর্কে জেনেছি। চল আমরা এই গ্রাফের অ্যাডজেসেন্সি লিস্ট বের করে ফেলি।

নোড	লিস্ট
০	১,২,৩
১	০,২
২	০,১,৪
৩	০,৪
৪	২,৩

বিএফএস ট্রাভারসালে একটি কথা সবসময় মনে রাখতে হবে যে কোনো নোডে ১ বারের বেশি যাওয়া যাবেনা। বিএফএস ট্রাভারসালে আমাদের একটি কিউ ডেটা স্ট্রাকচার ও একটি বুলিয়ান এ্যারে এর প্রয়োজন হবে। প্রথমে আমরা একটি ভিজিটেড বুলিয়ান এ্যারে নিব এবং শুরুতে সব নোড এর ভ্যালু false রাখব।

এবার একটি কিউ মেইনটেইন করব এবং সেখানে সোর্স ভ্যালুকে পুশ করে দেব। উপরের গ্রাফে আমাদের সোর্স ভ্যালু ০ । তাই ০ কে কিউতে পুশ করব।

এবার কিউতে পুশ করার সাথে সাথেই ভিজিটেড এ্যারেতে কিউ এর ফ্রন্ট ভ্যালুটা true করে দেব ও কিউ থেকে ওই ভ্যালুটা বের করে এনে ওর অ্যাডজেসেন্সি লিস্ট এর ভ্যালুগুলো কিউতে পুশ করে দেব এবং তাদের ভিজিটেড এ্যারেতে true করে দেব। এই অপারেশনের পর ভিজিটেড এ্যারে ও কিউ এর আপডেটেড অবস্থাঃ

এখন কিউ এর ফ্রন্ট ভ্যালুকে নেব। এই ক্ষেত্রে সেই ভ্যালু হচ্ছে ১। ১ কে কিউ থেকে বের করে আনব। ১ এর অ্যাডজেসেন্সি লিস্ট এ আনভিজিটেড নোডগুলো কিউতে পুশ করে দেব। এই ক্ষেত্রে ০ ও ২ অলরেডি ভিজিটেড তাই তারা পুশ হবে না।এই অপারেশনের পর ভিজিটেড এ্যারে ও কিউ এর আপডেটেড অবস্থাঃ

এখন কিউ এর ফ্রন্ট ভ্যালুকে নেব। এই ক্ষেত্রে সেই ভ্যালু হচ্ছে ২। ২ কে কিউ থেকে বের করে আনব। ২ এর অ্যাডজেসেন্সি লিস্ট এ আনভিজিটেড নোডগুলো কিউতে পুশ করে দেব। এই ক্ষেত্রে ০ ও ১ অলরেডি ভিজিটেড তাই তারা পুশ হবে না।তবে ৪ আনভিজিটেড তাই ৪ কে কিউতে পুশ করে দেব এবং ভিজিটেড এ্যারেতে ৪ কে true করে দেব। অপারেশনের পর ভিজিটেড এ্যারে ও কিউ এর আপডেটেড অবস্থাঃ

এখন কিউ এর ফ্রন্ট ভ্যালুকে নেব। এই ক্ষেত্রে সেই ভ্যালু হচ্ছে ৩। ৩ কে কিউ থেকে বের করে আনব। ৩ এর অ্যাডজেসেন্সি লিস্ট এ আনভিজিটেড নোডগুলো কিউতে পুশ করে দেব। এই ক্ষেত্রে ০ ও ৪ অলরেডি ভিজিটেড তাই তারা পুশ হবে না। অপারেশনের পর ভিজিটেড এ্যারে ও কিউ এর আপডেটেড অবস্থাঃ

এখন কিউ এর ফ্রন্ট ভ্যালুকে নেব। এই ক্ষেত্রে সেই ভ্যালু হচ্ছে ৪। ৪ কে কিউ থেকে বের করে আনব। ৪ এর অ্যাডজেসেন্সি লিস্ট এ আনভিজিটেড নোডগুলো কিউতে পুশ করে দেব। এই ক্ষেত্রে ২ ও ৩ অলরেডি ভিজিটেড তাই তারা পুশ হবে না। অপারেশনের পর ভিজিটেড এ্যারে ও কিউ এর আপডেটেড অবস্থাঃ

এখন খেয়াল করে দেখো যে কিউটি খালি হয়ে গেছে এবং সব নোড ভিজিটেড হয়ে গেছে। তার মানে আমাদের বিএফএস ট্রাভারসাল সম্পন্ন হয়েছে।

এবার আমরা যদি অর্ডারটা খেয়াল করি তাহলে দেখবেঃ

০->১->২->৩->৪

এইটি হচ্ছে উপরে প্রদত্ত গ্রাফের জন্য বিএফএস ট্রাভারসাল।