ধরুন একটি গ্রাফ আছে কিছু নোড এবং সংযুক্ত এজ সহ। প্রতিটি এজের বাইনারি ওয়েট আছে। অর্থাৎ ওয়েট হবে ০ বা ১। একটি সোর্স ভার্টেক্স দেওয়া আছে। আমাদের সোর্স থেকে অন্য সব ভার্টেক্স পর্যন্ত শর্টেস্ট পাথ বের করতে হবে। ধরুন গ্রাফটি নিচের মতো −
সাধারণ বিএফএস এলগরিদমে সব এজের ওয়েট সমান। এখানে কিছু ০ এবং কিছু ১। প্রতিটি ধাপে আমরা অপ্টিমাল ডিস্ট্যান্স কন্ডিশন চেক করব। এখানে ডবল-এন্ডেড কিউ (deque) ব্যবহার করে নোড স্টোর করব। এজের ওয়েট চেক করব। যদি ০ হয়, তবে কিউয়ের ফ্রন্টে পুশ করব, অন্যথায় ব্যাকে। বিস্তারিত জানতে অ্যালগরিদম দেখুন।
অ্যালগরিদম
binaryBFS(src) −
শুরু dist অ্যারে ডিক্লেয়ার করুন যেটি সোর্স থেকে ভার্টেক্স i-এর দূরত্ব dist[i]-তে স্টোর করবে। প্রাথমিকভাবে ইনফিনিটি দিয়ে ফিল করুন dist[src] := 0 src কিউ Q-তে ইনসার্ট করুন v := Q-র প্রথম এলিমেন্ট, এবং কিউ থেকে ডিলিট করুন while Q খালি নয়, do v-এর সব সংযুক্ত এজ e এর জন্য, do if v থেকে i-এর ওয়েট > dist[v] + v থেকে i-এর ওয়েট, then ওয়েট আপডেট করুন যদি ওয়েট ০ হয়, তবে ফ্রন্টে স্টোর করুন, অন্যথায় ব্যাকে end if done done dist অ্যার থেকে সব দূরত্ব প্রিন্ট করুন শেষ
উদাহরণ
#include<iostream> #include<vector> #include<deque> #define V 8 using namespace std; struct node { int next, weight; }; vector <node> edges[V]; void binaryBFS(int src) { int dist[V]; for (int i=0; i<V; i++) // প্রাথমিকভাবে ইনফিনিটি dist[i] = INT_MAX; deque <int> Q; dist[src] = 0; // সোর্স থেকে সোর্সের দূরত্ব ০ Q.push_back(src); while (!Q.empty()) { int v = Q.front(); // প্রথম ভার্টেক্স ডিলিট করে v-তে স্টোর Q.pop_front(); for (int i=0; i<edges[v].size(); i++) { // অপ্টিমাল ডিস্ট্যান্স চেক if (dist[edges[v][i].next] > dist[v] + edges[v][i].weight) { dist[edges[v][i].next] = dist[v] + edges[v][i].weight; if (edges[v][i].weight == 0) // ০ ওয়েট এজ ফ্রন্টে, অন্যথায় ব্যাকে Q.push_front(edges[v][i].next); else Q.push_back(edges[v][i].next); } } } for (int i=0; i<V; i++) cout << dist[i] << " "; } void addEdge(int u, int v, int wt) { edges[u].push_back({v, wt}); edges[v].push_back({u, wt}); } int main() { addEdge(0, 1, 0); addEdge(0, 3, 1); addEdge(0, 4, 0); addEdge(1, 2, 1); addEdge(1, 7, 0); addEdge(2, 5, 1); addEdge(2, 7, 0); addEdge(3, 4, 0); addEdge(3, 6, 1); addEdge(4, 6, 1); addEdge(5, 7, 1); addEdge(6, 7, 1); int src = 6; binaryBFS(src); }
আউটপুট
1 1 1 1 1 2 0 1
