इस समस्या में हमें एक निर्देशित ग्राफ़ दिया जाता है और हमें स्रोत से ग्राफ़ के गंतव्य तक के सभी पथों को प्रिंट करना होता है।
निर्देशित ग्राफ़ किनारों वाला एक ग्राफ़ है जो शीर्ष a से b तक निर्देशित होता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं
स्रोत =के गंतव्य =पी
आउटपुट:
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