क्रुस्कल का एल्गोरिदम भूलभुलैया जनरेटर

क्रुस्कल का एल्गोरिदम एक मिनिमम स्पैनिंग ट्री एल्गोरिदम है जिसे मेज़ बनाने के लिए इस्तेमाल किया जा सकता है। यह खास तौर पर परफेक्ट मेज़ बनाने के लिए असरदार है। क्रुस्कल के एल्गोरिदम का एक विकल्प प्रिम का एल्गोरिदम है, जो भी एक मिनिमम स्पैनिंग ट्री एल्गोरिदम है, लेकिन क्योंकि वे एक जैसे मेज़ बनाते हैं और क्रुस्कल का एल्गोरिदम तेज़ी से चलता है, इसलिए मैंने प्रिम को लागू करने की ज़हमत नहीं उठाई।

एक आदर्श भूलभुलैया वह भूलभुलैया होती है जिसमें भूलभुलैया के किसी भी बिंदु से किसी अन्य बिंदु तक जाने के लिए बिल्कुल एक ही रास्ता होता है। इसका मतलब है कि आप चक्कर लगाते हुए नहीं रह सकते, लेकिन आप अक्सर ऐसे रास्ते पर आएँगे जहाँ आपको पीछे मुड़ना होगा और वापस लौटना होगा।

यहाँ बनाए गए भूलभुलैया मानचित्रों में बिना किसी आरंभ और समाप्ति स्थिति के एक डिफ़ॉल्ट संस्करण शामिल है, इसलिए आप उन्हें स्वयं तय कर सकते हैं: भूलभुलैया के किसी भी बिंदु से किसी भी अन्य बिंदु तक एक समाधान होगा। यदि आप प्रेरणा चाहते हैं, तो आप सुझाए गए आरंभ और समाप्ति स्थिति को सक्षम कर सकते हैं - और यहां तक ​​कि दोनों के बीच समाधान भी देख सकते हैं।

क्रुस्कल के एल्गोरिदम के बारे में

क्रुस्कल का एल्गोरिदम जोसेफ बर्नार्ड क्रुस्कल, जूनियर ने बनाया था, जो एक अमेरिकी मैथमैटिशियन, स्टैटिस्टिशियन और कंप्यूटर साइंटिस्ट थे। उन्होंने सबसे पहले 1956 में अपने पेपर "ऑन द शॉर्टेस्ट स्पैनिंग सबट्री ऑफ़ ए ग्राफ एंड द ट्रैवलिंग सेल्समैन प्रॉब्लम" में एल्गोरिदम के बारे में बताया था।

यह एल्गोरिदम एक ग्राफ का मिनिमम स्पैनिंग ट्री (MST) ढूंढने के लिए डिज़ाइन किया गया है, जिससे यह पक्का होता है कि सभी वर्टिसेस कम से कम टोटल एज वेट से जुड़े हों और साइकल से बचा जा सके।

मेज़ जेनरेशन के लिए क्रुस्कल का एल्गोरिदम कैसे काम करता है

चरण 1: आरंभ करें

• भूलभुलैया में हर सेल को एक अलग सेट (एक यूनिक कंपोनेंट) मानें।
• आस-पास के सेल्स के बीच की सभी दीवारों को पोटेंशियल किनारों के तौर पर लिस्ट करें।

स्टेप 2: दीवारों को सॉर्ट करें

• दीवारों को शफ़ल करें या रैंडम तरीके से क्रम में लगाएं। अगर इसे असली क्रुस्कल एल्गोरिदम के तौर पर इस्तेमाल कर रहे हैं, तो दीवारों को रैंडम क्रम में सॉर्ट करें (क्योंकि मेज़ बनाने के लिए वेट की ज़रूरत नहीं होती है)।

स्टेप 3: दीवारों को प्रोसेस करें

• इधर-उधर की दीवारों से गुज़रें।
• अगर दीवार से बंटे दो सेल अलग-अलग सेट के हैं (यानी, वे अभी तक भूलभुलैया में जुड़े नहीं हैं), तो दीवार हटा दें और सेट को मिला दें।
• अगर वे पहले से ही एक ही सेट में हैं, तो दीवार को छोड़ दें (साइकिल से बचने के लिए)।

स्टेप 4: पूरा होने तक जारी रखें

• इस प्रोसेस को तब तक दोहराएं जब तक सभी सेल कनेक्ट न हो जाएं, जिससे एक सिंगल स्पैनिंग ट्री बन जाए।
• आखिर में, हर सेल बिना किसी लूप या अलग सेक्शन के दूसरे सेल से जुड़ा होता है।

क्योंकि क्रुस्कल का एल्गोरिदम मर्जिंग सेट्स पर निर्भर करता है, इसलिए इसे यूनियन-फाइंड एल्गोरिदम का इस्तेमाल करके ऑप्टिमाइज़ किया जा सकता है, जो मेज़ जेनरेशन के दौरान कनेक्टेड सेल्स को ट्रैक करने का एक अच्छा तरीका देता है। आप यूनियन-फाइंड एल्गोरिदम का मेरा PHP इम्प्लीमेंटेशन यहाँ देख सकते हैं: लिंक

अग्रिम पठन

यदि आपको यह पोस्ट पसंद आई हो, तो आपको ये सुझाव भी पसंद आ सकते हैं:

• एलर का एल्गोरिथम भूलभुलैया जेनरेटर
• बढ़ते पेड़ एल्गोरिथ्म भूलभुलैया जनरेटर
• रिकर्सिव बैकट्रैकर भूलभुलैया जनरेटर