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