एक ग्राफ ट्री होता है यदि उसमें कोई साइकिल नहीं होती। यह एक C++ प्रोग्राम है जो DFS का उपयोग करके जांचता है कि कोई डायरेक्टेड ग्राफ ट्री है या नहीं।
एल्गोरिदम
Begin function cyclicUtil() : a) वर्तमान नोड को विज़िटेड और रिकर्सन स्टैक का हिस्सा मार्क करें b) इस वर्टेक्स से सटे सभी वर्टेक्स के लिए पुनरावृत्ति करें। c) वर्टेक्स को रिकर्सन स्टैक से हटाएं। function cyclic() : a) सभी वर्टेक्स को नॉट विज़िटेड और रिकर्सन स्टैक का हिस्सा नहीं मार्क करें b) अलग-अलग ट्री में साइकिल का पता लगाने के लिए CyclicUtill() फंक्शन को कॉल करें End
उदाहरण
#include<iostream> #include <list> #include <limits.h> using namespace std; class G { int n; list<int> *adj; // आसन्न सूची संग्रहीत करें। bool CyclicUtil(int v, bool visited[], bool *rs); public: G(int V); // कंस्ट्रक्टर void addEd(int v, int w); bool cyclic(); }; G::G(int n) { this->n = n; adj = new list<int> [n]; } void G::addEd(int v, int u) // ग्राफ में एज जोड़ने के लिए { adj[v].push_back(u); // u को v की सूची में जोड़ें } bool G::CyclicUtil(int v, bool visited[], bool *recurS) { if (visited[v] == false) { visited[v] = true; // वर्तमान नोड को विज़िटेड और रिकर्सन स्टैक का हिस्सा मार्क करें recurS[v] = true; // इस वर्टेक्स से सटे सभी वर्टेक्स के लिए पुनरावृत्ति करें। list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { if (!visited[*i] && CyclicUtil(*i, visited, recurS)) return true; else if (recurS[*i]) return true; } } recurS[v] = false; // वर्टेक्स को रिकर्सन स्टैक से हटाएं। return false; } // जांचें कि ग्राफ ट्री है या नहीं bool G::cyclic() { // सभी वर्टेक्स को नॉट विज़िटेड और रिकर्सन स्टैक का हिस्सा नहीं मार्क करें bool *visited = new bool[n]; bool *recurS = new bool[n]; for (int i = 0; i < n; i++) { visited[i] = false; recurS[i] = false; } // अलग-अलग ट्री में साइकिल का पता लगाने के लिए CyclicUtill() फंक्शन को कॉल करें for (int i = 0; i < n; i++) if (CyclicUtil(i, visited, recurS)) return true; return false; } int main() { G g(4); g.addEd(0, 2); g.addEd(1, 2); g.addEd(2, 0); g.addEd(3, 2); if (g.cyclic()) cout << "Directed Graph isn't a tree"; else cout << "Directed Graph is a tree"; return 0; }
आउटपुट
Directed Graph isn't a tree
