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