ट्री के एज
कुल लंबाई
जाँचे गए एज

  • मौजूदा
  • ट्री में
  • साइकिल बनाएगा

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

क्रुस्कल एल्गोरिदम

क्रुस्कल एल्गोरिदम मिनिमम स्पैनिंग ट्री बनाता है, यानी एज का वह सबसे सस्ता समूह जो हर नोड को जोड़ता है, और वह भी सबसे आसान तरीके से: एज को सबसे छोटे से सबसे लंबे तक लें, और हर एज रखें, जब तक वह साइकिल न बनाए। चरण-दर-चरण देखें कि अलग-अलग हिस्से कैसे बढ़कर एक ट्री में मिलते हैं, और कौन-से एज छोड़े जाते हैं। ट्री को बढ़ते देखने के लिए “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। हर एज पर लिखी संख्या उसकी लंबाई है। ग्राफ़ के नीचे वे एज हैं जिन्हें अभी आज़माना है, सबसे छोटे से सबसे लंबे तक; जिस एज के दोनों सिरे पहले से जुड़े हों, वह साइकिल बनाएगा और लाल डैश वाली रेखा से बना होता है। “नया ग्राफ़” दूसरा ग्राफ़ बनाता है; उसमें कितने नोड और एज हों, यह चुनें। बोर्ड चुना होने पर, ऐरो कुंजियाँ एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।

यह कैसे काम करता है

  1. “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” का इस्तेमाल करें।
  2. कहीं भी जाने के लिए चरण स्लाइडर खींचें। जिन एज को अभी आज़माना है, वे ग्राफ़ के नीचे सूची में हैं, सबसे छोटा पहले।
  3. लाल डैश वाली रेखा से बने एज पर ध्यान दें: वे साइकिल बनाएँगे। “नया ग्राफ़” आज़माने के लिए दूसरा ग्राफ़ बनाता है।

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

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

यूनियन-फ़ाइंड

हर एज के लिए क्रुस्कल एल्गोरिदम को पूछना होता है कि उसके दोनों सिरे पहले से जुड़े हैं या नहीं। यूनियन-फ़ाइंड स्ट्रक्चर इसका जवाब जल्दी देता है: हर हिस्से का एक प्रतिनिधि नोड होता है, find लिंक के सहारे उस तक पहुँचता है, और union एक प्रतिनिधि को दूसरे से जोड़ देता है। दो आसान तरकीबों, पाथ कम्प्रेशन और साइज़ के हिसाब से यूनियन, से हर सवाल में लगभग स्थिर समय लगता है, इसलिए एज को क्रम में लगाना सबसे धीमा हिस्सा है, और उसका काम E log E के साथ बढ़ता है।

अक्सर पूछे जाने वाले प्रश्न

क्रुस्कल एल्गोरिदम क्या है?

एक ग्रीडी एल्गोरिदम जो सभी एज को सबसे छोटे से सबसे लंबे तक क्रम में लगाकर और हर वह एज जोड़कर मिनिमम स्पैनिंग ट्री बनाता है जो पहले चुने गए एज के साथ साइकिल नहीं बनाता।

क्रुस्कल एल्गोरिदम साइकिल का पता कैसे लगाता है?

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

क्रुस्कल एल्गोरिदम काम क्यों करता है?

साइकिल प्रॉपर्टी की वजह से: किसी भी साइकिल का सबसे लंबा एज मिनिमम स्पैनिंग ट्री के लिए कभी ज़रूरी नहीं होता। क्रुस्कल जो भी एज छोड़ता है, वह उस साइकिल का सबसे लंबा एज होता है जिसे वह बनाता, क्योंकि उससे पहले के सभी एज छोटे या बराबर थे।

प्रिम की जगह क्रुस्कल कब इस्तेमाल करें?

क्रुस्कल एल्गोरिदम आसान है और स्पार्स ग्राफ़ पर तेज़ है, और सीधे एज की सादी सूची पर काम करता है। प्रिम एल्गोरिदम डेंस ग्राफ़ और एडजेसेंसी लिस्ट के रूप में रखे ग्राफ़ के लिए ठीक है। दोनों एक ही कुल लंबाई का ट्री ढूँढते हैं।

क्या मेरा ग्राफ़ कहीं भेजा जाता है?

नहीं। ग्राफ़ और ट्री आपके ब्राउज़र में ही बनते हैं, और आपकी पिछली सेटिंग इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

एडिटर पर जाएँ