डेप्थ फर्स्ट सर्च (डीएफएस) ट्रैवर्सल एल्गोरिथम का उपयोग करके हम एक निर्देशित ग्राफ में चक्रों का पता लगा सकते हैं। यदि किसी नोड में कोई सेल्फ-लूप है, तो उसे एक चक्र माना जाएगा, अन्यथा, जब चाइल्ड नोड के पास अपने पैरेंट को जोड़ने के लिए एक और किनारा होगा, तो यह भी एक चक्र होगा।
डिस्कनेक्ट किए गए ग्राफ के लिए, अलग-अलग पेड़ मौजूद हो सकते हैं, हम उन्हें जंगल कह सकते हैं। अब हमें जंगल के सभी पेड़ों के लिए साइकिल का पता लगाना है।
इस दृष्टिकोण में, हम डीएफएस ट्रैवर्सल करने के लिए नोड्स असाइन करने के लिए विभिन्न सेटों का उपयोग करेंगे। तीन अलग-अलग सेट हैं, व्हाइट, ग्रे और ब्लैक। प्रारंभ में, सभी नोड्स सफेद सेट के अंदर संग्रहीत किए जाएंगे। जब एक नया नोड ट्रेस किया जाता है, तो इसे ग्रे सेट में संग्रहीत किया जाएगा और सफेद नोड से हटा दिया जाएगा। और बैकट्रैकिंग पूरा करने के बाद, जब उस नोड के लिए वह कार्य पूरा हो जाएगा, तो इसे ग्रे से ब्लैक सेट में बदल दिया जाएगा।
इनपुट और आउटपुट
इनपुट:आसन्नता मैट्रिक्स.0 1 0 0 00 0 0 0 01 0 0 1 00 0 0 0 10 0 1 0 0आउटपुट:ग्राफ में चक्र है।
एल्गोरिदम
dfs(curr, wSet, gSet, bSet)
इनपुट: वर्तमान नोड, सफ़ेद, धूसर और काला सेट।
आउटपुट: सच है अगर कोई चक्र है।
जबकि सेट से curr को हटाना शुरू करें और ग्राफ में curr से जुड़े सभी नोड्स v के लिए ग्रे सेट में जोड़ें, अगर v काले सेट में है, तो अगले भाग को छोड़ दें, और अगले पुनरावृत्ति के लिए जाएं यदि v है ग्रे सेट में, फिर सही लौटें यदि dfs(v, wSet, gSet, bSet) सत्य है, तो ग्रे सेट से ट्रू किया हुआ डिलीट करें और ब्लैक सेट में जोड़ें रिटर्न fasleEnd
हैसाइकिल(ग्राफ)
इनपुट - दिया गया ग्राफ़।
आउटपुट: सही है जब ग्राफ़ साइकिल चला रहा है।
शुरू में सफेद सेट में सभी नोड्स डालें, जबकि सफेद सेट में कुछ तत्व हैं, ग्राफ में सभी नोड्स v के लिए करें, अगर v सफेद सेट में नहीं है, तो अगर dfs(v, wSet, gSet, bSet) , फिर सच हो गया वापस लौटें झूठी अंत
उदाहरण
<पूर्व>#शामिल करेंआउटपुट
ग्राफ़ में चक्र होता है।