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

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

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

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

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

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

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

भूलभुलैया निर्माण के लिए क्रुस्कल का एल्गोरिदम कैसे काम करता है

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

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

चरण 2: दीवारों को क्रमबद्ध करें

• दीवारों को फेरबदल करें या बेतरतीब ढंग से क्रमबद्ध करें। यदि इसे एक सच्चे क्रुस्कल एल्गोरिथ्म के रूप में लागू किया जाता है, तो दीवारों को यादृच्छिक क्रम में क्रमबद्ध करें (क्योंकि भूलभुलैया निर्माण के लिए भार की आवश्यकता नहीं होती है)।

चरण 3: दीवारों की प्रक्रिया

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

चरण 4: पूरा होने तक जारी रखें

• इस प्रक्रिया को तब तक दोहराएं जब तक कि सभी कोशिकाएं जुड़कर एक एकल फैले हुए वृक्ष का निर्माण न कर लें।
• अंत में, प्रत्येक कोशिका बिना किसी लूप या पृथक खंड के अन्य कोशिकाओं से जुड़ी होती है।

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