इस समस्या में हमें एक निर्देशित ग्राफ दिया गया है और हमें ब्रेडथ फर्स्ट सर्च (BFS) का उपयोग करके ग्राफ के स्रोत से गंतव्य तक सभी पथ प्रिंट करने हैं।
निर्देशित ग्राफ एक ग्राफ है जिसमें किनारे शीर्ष a से b की ओर निर्देशित होते हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं -
स्रोत = K गंतव्य = P
आउटपुट
K -> T -> Y -> A -> P K -> T -> Y -> P K -> A -> P
यहां, हमने K से P तक के पथ ढूंढे हैं। हमने पथों को पार किया और K से उन सभी पथों को प्रिंट किया जो हमें P की ओर ले जाते हैं।
स्रोत से गंतव्य तक सभी पथ प्रिंट करने के लिए, हमें ग्राफ को पार करना होगा और पथों को संग्रहीत करना होगा और फिर वैध पथ प्रिंट करने होंगे।
DFS का उपयोग करने के मामले में, प्रक्रिया आसान है लेकिन इस मामले में इसे लागू करना थोड़ा मुश्किल है।
इस समस्या को हल करने के लिए, हमें एक कतार की आवश्यकता होगी जो पथों को संग्रहीत करेगी। स्रोत नोड से शुरू करके हम BFS का उपयोग करके सरणी को पार करना शुरू करेंगे। कतार में जांच करें। यदि गंतव्य शीर्ष पहुंच जाता है तो कतार के तत्वों को प्रिंट करें अन्यथा अनदेखा करें।
उदाहरण
नीचे दिया गया प्रोग्राम समाधान को और स्पष्ट करेगा -
#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
