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