साइकल डिटेक्शन (Cycle Detection)

परिचय

• इस लेक्चर में डायरेक्टेड ग्राफ में साइकल डिटेक्शन के बारे में चर्चा की जाएगी।

ग्राफ की संरचना

• ग्राफ में नोड्स और उनके बीच के कनेक्शन को दर्शाया गया है।
• उदाहरण के लिए, नोड्स को नाम दिया गया है: 1, 2, 3, 4, 5, 6, 7, 8।
• ग्राफ में साइकल की पहचान करने के लिए डीएफएस (DFS) एल्गोरिदम का उपयोग किया जाएगा।

डीएफएस एल्गोरिदम

• पिछले लेक्चर में अन्डायरेक्टेड ग्राफ में जो लॉजिक इस्तेमाल किया गया था, वही लॉजिक यहां नहीं लगाया जा सकता।
• डायरेक्टेड ग्राफ में साइकल डिटेक्शन के लिए विशेष सावधानी बरतने की आवश्यकता है।

साइकल की पहचान करने का तरीका

1. नोड्स को विजिटेड मार्क करना:
   • जब डीएफएस कॉल की जाती है, तो नोड को विजिटेड मार्क किया जाता है।
2. पैरेंट चेक करना:
   • यदि कोई नोड पहले से विजिटेड है, और वह पैरेन्ट नहीं है, तो साइकल मौजूद है।

कोडिंग प्रक्रिया

• ग्राफ की एडजेसेंसी लिस्ट बनाई जाती है।
• DFS कॉल के लिए एक फंक्शन बनाया जाता है।
• सभी नोड्स पर DFS कॉल की जाती है।
• साइकल मिलने पर ट्रू रिटर्न किया जाता है।
• यदि नोड विजिटेड नहीं है, तो DFS कॉल की जाती है।

टाइम और स्पेस कॉम्प्लेक्सिटी

• टाइम कॉम्प्लेक्सिटी: O(V + E) (जहाँ V नोड्स और E एजेस हैं)
• स्पेस कॉम्प्लेक्सिटी: लीनियर (O(V)) डेटा स्ट्रक्चर के लिए।

निष्कर्ष

• इस लेक्चर में हमने डायरेक्टेड ग्राफ में साइकल डिटेक्शन के लिए डीएफएस एल्गोरिदम का उपयोग किया।
• अगले वीडियो में BFS के माध्यम से साइकल डिटेक्शन की चर्चा करेंगे।

धन्यवाद

• मिलते हैं अगले वीडियो में!