इस प्रोग्राम में हम दिए गए ग्राफ पर DFS का उपयोग करके दो नोड्स के बीच पाथ मौजूद है या नहीं पता लगा सकते हैं।
एल्गोरिदम
Begin function isReach() एक रिकर्सिव फंक्शन है जो जांचता है कि d, s से पहुंच योग्य है या नहीं: A) सभी वर्टेक्स को अनविज़िटेड मार्क करें। B) वर्तमान नोड को विज़िटेड मार्क करें और इसे एनक्यू करें और इसका उपयोग वर्टेक्स के सभी आसन्न वर्टेक्स प्राप्त करने के लिए किया जाएगा C) क्यू से एक वर्टेक्स डीक्यू करें और प्रिंट करें D) डीक्यू किए गए वर्टेक्स s के सभी आसन्न वर्टेक्स प्राप्त करें E) यदि एक आसन्न विज़िट नहीं किया गया है, तो इसे विज़िटेड मार्क करें और एनक्यू करें F) यदि यह आसन्न नोड डेस्टिनेशन नोड है, तो सच लौटाएं अन्यथा BFS जारी रखें End
उदाहरण
#include <iostream> #include <list> using namespace std; class G { int n; list<int> *adj; public: //फंक्शन की घोषणा G(int n); void addEd(int v, int u); bool isReach(int s, int d); }; G::G(int n) { this->n = n; adj = new list<int> [n]; } void G::addEd(int v, int u) //ग्राफ में एज जोड़ें { adj[v].push_back(u); } bool G::isReach(int s, int d) { if (s == d) return true; //सभी वर्टेक्स को अनविज़िटेड मार्क करें। bool *visited = new bool[n]; for (int i = 0; i < n; i++) visited[i] = false; list<int> queue; //वर्तमान नोड को विज़िटेड मार्क करें और एनक्यू करें और इसका उपयोग वर्टेक्स के सभी आसन्न वर्टेक्स प्राप्त करने के लिए किया जाएगा visited[s] = true; queue.push_back(s); list<int>::iterator i; while (!queue.empty()) { s = queue.front(); queue.pop_front(); //क्यू से वर्टेक्स डीक्यू करें और प्रिंट करें //यदि एक आसन्न विज़िट नहीं किया गया है, तो इसे विज़िटेड मार्क करें और एनक्यू करें for (i = adj[s].begin(); i != adj[s].end(); ++i) { if (*i == d) return true; // यदि यह आसन्न नोड डेस्टिनेशन नोड है, तो सच लौटाएं अन्यथा BFS जारी रखें if (!visited[*i]) { visited[*i] = true; queue.push_back(*i); } } } return false; } int main() { G g(4); g.addEd(1, 3); g.addEd(0, 1); g.addEd(2, 3); g.addEd(1, 0); g.addEd(2, 1); g.addEd(3, 1); cout << "Enter the source and destination vertices: (0-3)"; int a, b; cin >> a >> b; if (g.isReach(a, b)) cout << "\nThere is a path from " << a << " to " << b; else cout << "\nThere is no path from " << a << " to " << b; int t; t = a; a = b; b = t; if (g.isReach(a, b)) cout << "\nThere is a path from " << a << " to " << b; else cout << "\nThere is no path from " << a << " to " << b; return 0; }
आउटपुट
Enter the source and destination vertices: (0-3) There is a path from 3 to 1 There is a path from 1 to 3
