এই সমস্যাতে, আমাদের একটি ডায়रेक्टেড গ্রাফ দেওয়া আছে যা অডজেসেন্সি লিস্ট (adjacency list) আকারে রিপ্রেজেন্ট করা। আমাদের কাজ হল BFS ব্যবহার করে একটি ভার্টেক্স থেকে বাকি সব ভার্টেক্সে পথ বের করার প্রোগ্রাম তৈরি করা।
BFS (Breadth First Search) হল একটি অ্যালগরিদম যা গ্রাফকে ব্রেডথওয়ার্ড মোশনে ট্রাভার্স করে এবং একটি কিউ ব্যবহার করে নেক্সট ভার্টেক্স মনে রাখে সার্চ শুরু করার জন্য, যখন কোনো ইটারেশনে ডেড এন্ড হয়।
উদাহরণ দেখি:
ইনপুট -
আউটপুট
S
A <= S
B <= A <= S
C <= S
D <= C <= S
সমাধানের পদ্ধতি
সমাধানের জন্য, আমরা গ্রাফের প্রতিটি এলিমেন্টে BFS সার্চ অ্যালগরিদম পারফর্ম করব। এই কাজের জন্য, আমরা একটি কিউ তৈরি করব যেটি যেকোনো নোডে ভিজিটের ফ্ল্যাগ স্টোর করবে। তারপর, একটি ভিজিটেড অ্যারে ব্যবহার করে চেক করব যে এলিমেন্টটি ভিজিটেড কিনা (বাইনারি ভ্যালু ০ এবং ১ দিয়ে ভিজিট ডিনোট করা)।
এখন, আমরা উদাহরণটি ধাপে ধাপে সমাধান করব:
নোড S থেকে শুরু করলে,
নোড A-তে সরাসরি যাব।
নোড B-এ যেতে হলে প্রথমে নোড A-তে যাব, তারপর A ট্রাভার্স করে B-এ যাব।
নোড C-এ যেতে হলে S থেকে সরাসরি C-এ যাব।
নোড D-এ যেতে হলে প্রথমে নোড C-এ যাব, তারপর D-এ যাব।
উদাহরণ
#include <bits/stdc++.h> using namespace std; void printPath(vector<int> parent, int initial, int node){ while (initial != node){ cout<<node<<" <= "; node = parent[node]; } cout<<node<<endl; } void findPathBFS(vector<vector<int> > graphAdjList, int initial, int graphSize){ vector<int> parent(graphSize, 0); vector<int> queue(graphSize, 0); int front = -1, rear = -1; vector<int> isVisited(graphSize, 0); isVisited[0] = 1; parent[0] = initial; queue[++rear] = initial; int k; while (front != rear) { k = queue[++front]; for (int j:graphAdjList[k]){ if (isVisited[j] == 0){ queue[++rear] = j; isVisited[j] = 1; parent[j] = k; } } } for (k = 0; k < graphSize; k++) printPath(parent, initial, k); } int main(){ vector<vector<int> > graphAdjList; graphAdjList.push_back({1, 3}); graphAdjList.push_back({0, 2}); graphAdjList.push_back({1}); graphAdjList.push_back({4}); graphAdjList.push_back({0}); int graphSize = graphAdjList.size(); int initial = 0; cout<<"The Path from vertex '0' to all other vertex in the graph is : \n"; findPathBFS(graphAdjList, initial, graphSize); }
আউটপুট
The Path from vertex '0' to all other vertex in the graph is : 0 1 <= 0 2 <= 1 <= 0 3 <= 0 4 <= 3 <= 0
