এই সমস্যায়, আমাদের একটি সংলগ্ন তালিকা হিসাবে উপস্থাপিত একটি নির্দেশিত গ্রাফ দেওয়া হয়েছে। আমাদের কাজ হল BFS ব্যবহার করে একটি শিরোনাম থেকে বিশ্রামের পথ খোঁজার জন্য একটি প্রোগ্রাম তৈরি করা .
BFS (ব্রেডথ ফার্স্ট সার্চ) হল একটি অ্যালগরিদম যা একটি প্রশস্ত গতিতে একটি গ্রাফকে অতিক্রম করে এবং একটি সারি ব্যবহার করে একটি অনুসন্ধান শুরু করার জন্য পরবর্তী শীর্ষটি মনে রাখার জন্য, যখন কোনো পুনরাবৃত্তিতে একটি শেষ প্রান্ত ঘটে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট −
আউটপুট
এস
A <=S
B <=A <=S
C <=S
D <=C <=S
সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমরা গ্রাফের প্রতিটি উপাদানে BFS অনুসন্ধান অ্যালগরিদম সম্পাদন করব। কাজটি সম্পাদন করার জন্য, আমরা একটি সারি তৈরি করব যা যেকোনো নোডে ভিজিট করার জন্য পতাকা সংরক্ষণ করবে। তারপর, একটি পরিদর্শন করা অ্যারে ব্যবহার করে আমরা উপাদানটি পরিদর্শন করা হয়েছে কিনা তা পরীক্ষা করব (বাইনারী মান 0 এবং 1 ভিজিট নির্দেশ করে)।
এখন, আমরা আমাদের সমাধানের কাজ বোঝার জন্য ধাপে ধাপে উদাহরণটি সমাধান করব,
নোড S,
থেকে শুরু-
আমরা সরাসরি নোড এ পরিদর্শন করব।
-
নোড বি-তে পৌঁছানোর জন্য, আমরা প্রথমে নোড এ পরিদর্শন করব তারপর নোড বি ট্রাভার্সিং নোড এ পৌঁছাব।
-
নোড C-এ পৌঁছানোর জন্য, আমরা সরাসরি S থেকে C পরিদর্শন করব।
-
নোড ডি তে পৌঁছানোর জন্য, আমরা প্রথমে নোড সি এবং তারপর নোড ডি
পরিদর্শন করব
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#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
