মডিউল ২_০ঃ ব্রেডথ ফার্স্ট সার্চ কি?

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

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

একটি রিয়েল লাইফ এক্সাম্পল দিয়ে বুঝা যাক।

ধরুন আপনি ঢাকায় থাকেন আর আপনি ছুটিতে কক্সবাজার যেতে চান। আপনার কাছে দুইটি রাস্তা আছে। আপনি চাইলে ঢাকা থেকে কক্সবাজার চলে যেতে পারেন আবার চাইলে চট্টগ্রাম হয়ে কক্সবাজার যেতে পারেন। বিএফএস এই ক্ষেত্রে আপনাকে সব থেকে ছোট রাস্তাটি বের করে দেবে।