এই সমস্যায় আমাদের একটি নির্দেশিত গ্রাফ দেওয়া হয়েছে এবং আমাদের ব্রেডথ ফার্স্ট সার্চ (BFS) ব্যবহার করে উৎস থেকে গ্রাফের গন্তব্য পর্যন্ত সমস্ত পথ প্রিন্ট করতে হবে।
নির্দেশিত গ্রাফ প্রান্ত সহ একটি গ্রাফ যা শীর্ষবিন্দু a থেকে b পর্যন্ত নির্দেশিত।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক -
উৎস =K গন্তব্য =P
আউটপুট
K -> T -> Y -> A -> P K -> T -> Y -> P K -> A -> P
এখানে, আমরা K থেকে P পর্যন্ত পথ খুঁজে পেয়েছি। আমরা পথ অতিক্রম করেছি এবং K থেকে সমস্ত পথ প্রিন্ট করেছি যা আমাদেরকে P-তে নিয়ে যায়।
উত্স থেকে গন্তব্য পর্যন্ত সমস্ত পথ প্রিন্ট করতে, আমাদের গ্রাফটি অতিক্রম করতে হবে এবং পাথগুলি সঞ্চয় করতে হবে এবং তারপর বৈধ পথগুলি প্রিন্ট করতে হবে৷
DFS ব্যবহার করার ক্ষেত্রে, প্রক্রিয়াটি সহজ কিন্তু এই ক্ষেত্রে এটি বাস্তবায়ন করা একটু কঠিন।
এই সমস্যাটি সমাধান করার জন্য, আমাদের একটি সারি দরকার যা পাথ সংরক্ষণ করবে। সোর্স নোড থেকে শুরু করে আমরা BFS ব্যবহার করে অ্যারে অতিক্রম করা শুরু করব। অতিক্রম করুন
গাছটি এবং তারপর সারিতে চেক করুন৷ যদি গন্তব্য শীর্ষবিন্দুতে পৌঁছে যায় তাহলে সারির উপাদানগুলি মুদ্রণ করুন অন্যথায় এটি উপেক্ষা করুন৷
উদাহরণ
নিচের প্রোগ্রামটি সমাধানটিকে আরও স্পষ্ট করে −
#include <bits/stdc++.h>
using namespace std;
void printPath(vector<char>& path) {
int size = path.size();
for (int i = 0; i < size; i++)
cout<<path[i]<<" ";
cout<<endl;
}
int isVertexVisited(char x, vector<char>& path) {
int size = path.size();
for (int i = 0; i< size; i++)
if (path[i] == x)
return 1;
return 0;
}
void pathSourceToDestination(vector<vector<char> >&g, char src, char dst, int v) {
queue<vector<char> > q;
vector<char> path;
path.push_back(src);
q.push(path);
while (!q.empty()) {
path = q.front();
q.pop();
char last = path[path.size() - 1];
if (last == dst)
printPath(path);
for (int i = 0; i < g[last].size(); i++) {
if (!isVertexVisited(g[last][i], path)) {
vector<char> newpath(path);
newpath.push_back(g[last][i]);
q.push(newpath);
}
}
}
}
int main() {
vector<vector<char> > g;
int v = 4;
g.resize(4);
g['X'].push_back('S');
g['X'].push_back('A');
g['X'].push_back('N');
g['A'].push_back('S');
g['N'].push_back('X');
g['N'].push_back('A');
char src = 'N', dst = 'S';
cout<<"path from src "<<src<<" to dst "<<dst<<" are \n";
pathSourceToDestination(g, src, dst, v);
return 0;
} আউটপুট
path from src N to dst S are N X S N A S N X A S
