বিএফএস (BFS) বা ব্রেডথ ফাস্ট সার্চ (Breadth First Search) হলো গ্রাফ এর মধ্যে কোনোকিছু খুজে বের করার অনেকগুলো অ্যালগরিদম এর একটি। গ্রাফ এ এক নোড থেকে আরেক নোড এ যাওয়ার ক্ষুদ্রতম পথ খুজে বের করতে আমরা বিএফএস ব্যবহার করে থাকি। বিএফএস শুধুমাত্র আনঅয়েটেড গ্রাফে কাজ করে। মানে এক নোড থেকে আরেক নোড এ যাওয়ার কস্ট (cost) হতে হয় ১। এক নোড থেকে আরেক নোডে যাওয়ার যে সংক্ষিপ্ততম পাথ বা রাস্তা তা বিএফএস দিয়ে বের করা যাবে।
আগের পর্বে আমরা গ্রাফ এর বেসিক কিছু জিনিস নিয়ে কথা বলেছিলাম। ঐ পোস্ট টা এখানে পাবেন।
উপরের চিত্রে নোড ১ থেকে নোড ৫ এ যাওয়ার ক্ষুদ্রতম পথ হলো, ১->২->৪->৫। যদিও দুটি নোডের মধ্যে একাধির শর্টেস্ট পাথ থাকতে পারে, বিএফএস শেষে আমরা একটি পাথ পাবো। এই পাথ এবং এর নোড গুলো নিয়ে গঠিত ট্রি কে বলা হয় বিএফএস ট্রি।
গ্রাফে বিএফএস চালানোর আগে আমরা কিছু জিনিস বুঝে নেই
- যেখান থেকে বিএফএস শরু হবে (Source node) তার লেভেল হলো শুন্য (০)।
- সোর্স নোড থেকে যে নোডগুলিতে সরাসরি যাওয়া যাবে তার লেভেল হলো ১।
- এভাবে লেভেল ১ এর নোড গুলা থেকে যেই নোডগুলিতে সরাসরি যাওয়া যাবে তার লেভেল হবে ২।
- আমরা কখনোও একটি নোড একাধিকবার ভিজিট করবো না।
- একটি নোড থেকে যে নোড গুলোতে যাওয়া যায় (পরবর্তী লেভেল নোড), সেই নোড গুলোকে একটা কিউ (Queue) তো রেখে দিবো। তারপর কিউ থেকে একটা একটা করে নোড বের করে এনে একই কাজ আবার করবো যতক্ষন সম্ভব হয় (যতক্ষন না গন্তব্যে পৌছি/যতক্ষন না সব নোড ভিজিট করা হয়)।
আমরা বিএফএস শিখবো কিছু চিত্রের মাধ্যমে। উপরের ছবিটিতে ধরা যাক আমরা নোড ১ থেকে নোড ৫ এ যেতে চাই। তাহলে,
প্রথমে আমাদের সোর্স নোড দেয়া হবে। একে আমরা কিউ (std::queue) তে রেখে দিবো ভিজিটেড হিসেবে।
এরপরের ধাপে আমরা একটি লুপ চালাবো যতক্ষন না পর্যন্ত আমাদের Queue খালি হয়ে যায়। আমরা নোড ১ কে কিউ থেকে বের করে নিয়ে এর সমস্ত অ্যাডজাসেন্ট নোড (লেভেল ১ নোড) কে কিউ তে রাখবো।
নোড ১ এর অ্যাডজাসেন্সি নোড হিসেবে নোড ২ কিউ তে এসে গেছে। এবার আমার ২ কে ভিজিটেড হিসেবে মার্ক করে নিবে এবং কিউ থেকে বের করে নিব। এর সমস্ত অ্যাডজাসেন্ট নোড কে লেভেল ২ নোড হিসেবে কিউ তে ঢুকিয়ে রাখবো।
নোড ২ এর অ্যাডজাসেন্ট নোড হিসেবে নোড ৩ এবং নোড ৪ কিউ তে এসে গেছে। এখন আমরা প্রথমে নোড ৩ কে তুলে নিয়ে ভিজিটেড হিসেবে মার্ক করবো এবং এর অ্যাডাসেন্ট নোড ৬ এবং ৭ কে কিউ তে রাখবো। এদের লেভেল হলো ৩।
এবার নোড ৪ এর পালা, ৩ এর মতো একেউ তুলে নিয়ে এর এডজাসেন্ট নোড ৫ কে কিউ রাখবো। যেহেতু নোড ৬ ইতোমধ্যে ভিজিটেড তাই একে আর আমরা কিউ তে রাখবো না। নোড ৫ এবং নোড ৬ উভয়ের লেভলই হলো ৩।
এবার আমরা আমাদের ডেস্টিনেশন নোড ৫ এ এসে গেছি। এখানে নোড ৫ এর লেভেল হলো ৩। সুতরাং সোর্স থেকে নোড ৫ এ আসার ক্ষদ্রতম পথ হলো ৩ দৈর্ঘ্য বিশিষ্ট।
এখানে আমাদের নোড ৫,৬ এবং ৭ এখনও আনভিজিটেড রয়ে গেছে। যদিও এদের ভিজিট করে কোন লাভ হবে না। তবুও নিচের চিত্রের মাধ্যমে দেখা যাক কি ঘটবে আসলে।
এতক্ষন দেখা গেলে বিএফএস আসলে কিভাবে কাজ করে। এখন কোড করার মাধ্যমে বুঝার চেষ্টা করি।
প্রথম অংশ
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | /* Sharif Hasan - CSE, PUST Apr 24, 2020 02: 14 PM */ #include<bits/stdc++.h> using namespace std; /*Main function*/ int main() { /* গ্রাফ টি আডজাসেন্সি লিস্ট এ রাখা */ vector <int> graph[8]; graph[1].push_back(2); graph[2].push_back(1); graph[2].push_back(3); graph[2].push_back(4); graph[3].push_back(2); graph[3].push_back(7); graph[3].push_back(6); graph[4].push_back(2); graph[4].push_back(5); graph[4].push_back(6); graph[5].push_back(4); graph[5].push_back(6); graph[6].push_back(3); graph[6].push_back(5); graph[6].push_back(4); graph[7].push_back(3); |
আমরা গ্রাফ নামের একটি অ্যারে নিয়েছি (লাইন ১৩), যাতে আমরা আমাদের আডজাসেন্সি নোড গুলো std::vector<int> এর মধ্যে আডজাসেন্সি লিস্ট আকারে জমা রাখবো। পরবর্তী লাইন গুলোতে আমরা এই কাজটাই করেছি। যেমন নোড ২ এর আডজাসেন্সি নোড হলো ১,৩,৪। আমি নোড ১,৩,৪ কে ২ এর লিস্ট এ ঢুকিয়ে রেখেছি।
দ্বিতীয় অংশ
| 1 2 3 | int level[8]; memset(level,-1,sizeof(level)); int targetNode=5; |
এখানে আমরা int level[8] নামে একটি অ্যারে নিয়েছি। এই অ্যারে টা প্রথমে -1 দিয়ে পূরণ করে নিয়েছি। কারণ এর অ্যারে টা একই সাথে আমাদের সোর্স থেকে টার্গেট নোড এর দূরত্ব নির্দেশ করবে এবং অ্যারে টা ভিজিট করেছি কিনা তাও নির্দেশ করবে। যদি লেভেল এর কোনও ইনডেক্স -1 না হয় তবে বুঝতে হবে ঐ নোড এখনও ভিজিট করা হয়নি।
তৃতীয় অংশ
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | queue <int> q; q.push(1); level[1]=0; while(!q.empty()){ int current=q.front(); q.pop(); if(current==targetNode){ cout<<"আমরা এখন নোড "<< current<<" এ আছি, উৎস থেকে ক্ষুদ্রতম দূরত্ব "<<level[current]; break; } for(int i=0;i<graph[current].size();i++){ if(level[graph[current][i]]==-1){ level[graph[current][i]]=level[current]+1; q.push(graph[current][i]); } } } return 0; } |
প্রথম লাইনে আমরা একটা std:queue<int> নিয়েছি। এখানে আমরা আমাদের নোড গুলো ভিজিট করার জন্য রাখবো। যেহেতু আমাদের সোর্স নোড হলো ১, তাই শুরুতে আমরা নোডটি কে std:queue<int> তে রেখে দিয়েছি। যেহেতু নোড ১ এর লেভেল ০,তাই level[1]=0;এর মাধ্যমে আমরা নোড ১ এর লেভেল ০ করে দিয়েছি। তারপর একটি লুপ চালিয়েছি,যা যতক্ষণ না পর্যন্ত আমাদের কিউ খালি হয়, ততক্ষণ পর্যন্ত চলবে। লুপ এর প্রথমেই int current=q.front(); এর মাধ্যমে আমরা কিউ এর স্যামনের ভ্যালুকে current ভ্যারিয়েবল এর রেখেছি এবং তারপর কিউ থেকে নোডটি ডিলিট করে দিয়েছি। তারপর দেখেছি আমরা আমাদের টার্গেট নোডে এসেছি কিনা। যদি এসে পরি তবে লুপ থেমে যাবে। নাহলে, ১১ নং লাইনে আমরা বর্তমান current নোড এর সবগুলো অ্যাডজাসেন্ট নোড কে লুপ এর মাধ্যমে দেখেছি এই নোড আগেই ভিজিট করা হয়েছি কি না (১২ নং লাইন)। যদি ভিজিট করা না হয় তবে তাকে আমরা ভিজিট করবো এবং level[graph[current][i]]=level[current]+1; এই লাইনের মাধ্যমে তার লেভেল আমরা current নোড এর চেয়ে ১ বেশি করে দিবো। সবশেষে নোডটিকে কিউ টে রেখে দিবো।
পরিশেষ
মোটামুটি এই হলো আমাদের বিএফএস কথন। আজকের লেখাটা আমার মনমতন লিখতে পারিনি। কারো কোনও বুঝার সমস্যা হলে ফেইসবুক বা এখানে কমেন্টে যেকোনো ভাবে প্রশ্ন করতে পারেন।
আরও পরুনঃ
গ্রাফ বেসিক: গ্রাফ এবং গ্রাফ এর রিপ্রেজেন্টেশন
ডাটা স্ট্রাকচার: সেগমেন্ট ট্রি লেজি প্রপাগেশন।
https://en.wikipedia.org/wiki/Breadth-first_search
১টি মন্তব্য