এই সমস্যায়, একটি ডিরেক্টেড গ্রাফ দেওয়া থাকে এবং আমাদের গ্রাফের সোর্স থেকে ডেস্টিনেশন পর্যন্ত সব পথ প্রিন্ট করতে হবে।
ডিরেক্টেড গ্রাফ হলো এমন একটি গ্রাফ যেখানে এজগুলো ভার্টেক্স a থেকে b-এ ডিরেক্টেড থাকে।
উদাহরণ দিয়ে বুঝি:
সোর্স = K ডেস্টিনেশন = P
আউটপুট:
K -> T -> Y -> A -> P K -> T -> Y -> P K -> A -> P
এখানে, আমরা K থেকে P পর্যন্ত পথ খুঁজে পেয়েছি। আমরা পথগুলো ট্রাভার্স করেছি এবং K থেকে P-এ যাওয়া সব পথ প্রিন্ট করেছি।
এই সমস্যাটি সমাধান করতে, আমরা ডেপথ-ফার্স্ট সার্চ ট্রাভার্সাল টেকনিক ব্যবহার করে গ্রাফ ট্রাভার্স করব। সোর্স থেকে শুরু করে, আমরা প্রতিটি ভার্টেক্স ট্রাভার্স করব, আমাদের পথ অ্যারেতে সংরক্ষণ করব এবং ভিজিটেড হিসেবে মার্ক করব (একই ভার্টেক্স বারবার ভিজিট না করার জন্য)। এবং পথটি প্রিন্ট করব, যখন ডেস্টিনেশন ভার্টেক্স পাওয়া যায়।
প্রোগ্রামটি দেখি যা লজিকটি ইমপ্লিমেন্ট করে:
C++ উদাহরণ
#include<iostream> #include <list> using namespace std; class Graph { int V; list<int> *adj; void findNewPath(int , int , bool [], int [], int &); public: Graph(int V); void addEdge(int u, int v); void printPaths(int s, int d); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int u, int v) { adj[u].push_back(v); } void Graph::printPaths(int s, int d) { bool *visited = new bool[V]; int *path = new int[V]; int path_index = 0; for (int i = 0; i < V; i++) visited[i] = false; findNewPath(s, d, visited, path, path_index); } void Graph::findNewPath(int u, int d, bool visited[], int path[], int &path_index) { visited[u] = true; path[path_index] = u; path_index++; if (u == d) { for (int i = 0; i<path_index; i++) cout<<path[i]<<" "; cout << endl; } else { list<int>::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) if (!visited[*i]) findNewPath(*i, d, visited, path, path_index); } path_index--; visited[u] = false; } int main() { Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(0, 3); g.addEdge(2, 0); g.addEdge(2, 1); g.addEdge(1, 3); int s = 2, d = 3; cout<<"Following are all different paths from source to destination : \n"; g.printPaths(s, d); return 0; }আউটপুট
Following are all different paths from source to destination: 2 0 1 3 2 0 3 2 1 3
