डीपथ फर्स्ट सर्च (DFS) ट्रैवर्सल एल्गोरिदम का उपयोग करके हम एक निर्देशित ग्राफ में चक्र का पता लगा सकते हैं। यदि किसी नोड में कोई सेल्फ-लूप है, तो इसे चक्र माना जाएगा, अन्यथा जब चाइल्ड नोड का अपने पैरेंट से जुड़ने के लिए एक और किनारा हो, तो यह भी एक चक्र होगा।
डिस्कनेक्टेड ग्राफ के लिए, अलग-अलग ट्री मौजूद हो सकते हैं, हम उन्हें एक वन कह सकते हैं। अब हमें वन के सभी ट्री के लिए चक्र का पता लगाना होगा।
इस दृष्टिकोण में, हम DFS ट्रैवर्सल करने के लिए नोड्स को असाइन करने के लिए विभिन्न सेटों का उपयोग करेंगे। तीन अलग-अलग सेट हैं: व्हाइट, ग्रे और ब्लैक। प्रारंभ में, सभी नोड्स व्हाइट सेट के अंदर संग्रहीत होंगे। जब एक नया नोड पार किया जाता है, तो इसे ग्रे सेट में संग्रहीत किया जाएगा और व्हाइट से हटा दिया जाएगा। और बैकट्रैकिंग पूरा होने के बाद, जब उस नोड के लिए कार्य पूरा हो जाता है, तो इसे ग्रे से ब्लैक सेट में स्वैप किया जाएगा।
इनपुट और आउटपुट
इनपुट: आसन्नता मैट्रिक्स। 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 आउटपुट: ग्राफ में चक्र है।
एल्गोरिदम
dfs(curr, wSet, gSet, bSet)
इनपुट: वर्तमान नोड, व्हाइट, ग्रे और ब्लैक सेट।
आउटपुट: यदि चक्र है तो सच।
शुरू curr को व्हाइट सेट से हटाएं और ग्रे सेट में जोड़ें ग्राफ में curr से जुड़े सभी नोड्स v के लिए, करें यदि v ब्लैक सेट में है, तो अगले भाग को छोड़ें, और अगले पुनरावृत्ति के लिए जाएं यदि v ग्रे सेट में है, तो वापस करें सच यदि dfs(v, wSet, gSet, bSet) सच है, तो वापस करें सच किया curr को ग्रे सेट से हटाएं और ब्लैक सेट में जोड़ें वापस करें गलत अंत
hasCycle(graph)
इनपुट: दिया गया ग्राफ।
आउटपुट: जब ग्राफ में चक्र हो तो सच।
शुरू प्रारंभ में सभी नोड्स को व्हाइट सेट में डालें जब व्हाइट सेट में कुछ तत्व हों, करें ग्राफ में सभी नोड्स v के लिए, करें यदि v व्हाइट सेट में नहीं है, तो यदि dfs(v, wSet, gSet, bSet), तो वापस करें सच किया किया वापस करें गलत अंत
उदाहरण
#include<iostream> #include<set> #define NODE 5 using namespace std; int graph[NODE][NODE] = { {0, 1, 0, 0, 0}, {0, 0, 0, 0, 0}, {1, 0, 0, 1, 0}, {0, 0, 0, 0, 1}, {0, 0, 1, 0, 0} }; bool dfs(int curr, set<int>&wSet, set<int>&gSet, set<int>&bSet) { //curr को व्हाइट सेट से ग्रे सेट में ले जाना। wSet.erase(wSet.find(curr)); gSet.insert(curr); for(int v = 0; v < NODE; v++) { if(graph[curr][v] != 0) { //सभी पड़ोसी शीर्षों के लिए if(bSet.find(v) != bSet.end()) continue; //यदि शीर्ष ब्लैक सेट में हैं if(gSet.find(v) != gSet.end()) return true; //यह एक चक्र है if(dfs(v, wSet, gSet, bSet)) return true; //चक्र मिला } } //v को ग्रे सेट से ब्लैक सेट में ले जाना। gSet.erase(gSet.find(curr)); bSet.insert(curr); return false; } bool hasCycle() { set<int> wSet, gSet, bSet; //तीन सेट व्हाइट, ग्रे और ब्लैक के रूप में for(int i = 0; i 0) { for(int current = 0; current < NODE; current++) { if(wSet.find(current) != wSet.end()) if(dfs(current, wSet, gSet, bSet)) return true; } } return false; } int main() { bool res; res = hasCycle(); if(res) cout << "The graph has cycle." << endl; else cout << "The graph has no cycle." << endl; }
आउटपुट
The graph has cycle.
