इस समस्या में हमें एक निर्देशित ग्राफ दिया गया है और हमें ग्राफ के स्रोत से गंतव्य तक सभी पथ प्रिंट करने हैं।
निर्देशित ग्राफ एक ग्राफ है जिसमें किनारे शीर्ष 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
