এই সমস্যায়, একটি ডিরেক্টেড গ্রাফ দেওয়া থাকে এবং আমাদের ব্রেডথ ফার্স্ট সার্চ (BFS) ব্যবহার করে গ্রাফের সোর্স থেকে ডেস্টিনেশন পর্যন্ত সব পথ প্রিন্ট করতে হবে।
ডিরেক্টেড গ্রাফ হলো এমন একটি গ্রাফ যেখানে এজগুলো ভার্টেক্স a থেকে b-এ ডিরেক্টেড থাকে।
উদাহরণ দিয়ে বুঝি:
সোর্স = K ডেস্টিনেশন = P
আউটপুট:
K -> T -> Y -> A -> P K -> T -> Y -> P K -> A -> P
এখানে, আমরা K থেকে P পর্যন্ত পথ খুঁজে পেয়েছি। আমরা পথগুলো ট্রাভার্স করেছি এবং K থেকে P-এ যাওয়া সব পথ প্রিন্ট করেছি।
সোর্স থেকে ডেস্টিনেশন পর্যন্ত সব পথ প্রিন্ট করতে, আমাদের গ্রাফ ট্রাভার্স করতে হবে এবং পথগুলো সংরক্ষণ করতে হবে এবং তারপর ভ্যালিড পথগুলো প্রিন্ট করতে হবে।
DFS এর ক্ষেত্রে প্রসেসটি সহজ কিন্তু BFS-এ এটি কিছুটা ট্রিকি ইমপ্লিমেন্ট করা।
এই সমস্যাটি সমাধান করতে, আমাদের একটি কিউ দরকার হবে যা পথগুলো সংরক্ষণ করবে। সোর্স নোড থেকে শুরু করে আমরা BFS ব্যবহার করে অ্যারে ট্রাভার্স করব। ট্রি ট্রাভার্স করব এবং কিউতে চেক করব। যদি ডেস্টিনেশন ভার্টেক্স পাওয়া যায় তবে কিউ এলিমেন্টগুলো প্রিন্ট করব অন্যথায় উপেক্ষা করব।
C++ উদাহরণ
#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
