क्रुस्कल एल्गोरिदम
एज को क्रम में लगाओ, सबसे छोटा लो, कभी लूप मत बनाओ। क्रुस्कल एल्गोरिदम शायद सबसे आसान ग्रीडी एल्गोरिदम है, फिर भी यह ग्राफ़ के हर नोड को जोड़ने का सबसे सस्ता तरीका हमेशा ढूँढ लेता है।
मूल विचार
मिनिमम स्पैनिंग ट्री वेटेड ग्राफ़ के हर नोड को सबसे कम संभव कुल एज लंबाई से जोड़ता है। क्रुस्कल एल्गोरिदम शुरुआत से एक ट्री नहीं बढ़ाता। यह पूरे ग्राफ़ को एक साथ देखता है, हर नोड को उसका अलग हिस्सा मानकर शुरू करता है, और उपलब्ध सबसे छोटे एज से हिस्सों को जोड़ता रहता है, जब तक सिर्फ़ एक हिस्सा न बचे।
चरण-दर-चरण
एज को सबसे छोटे से सबसे लंबे तक क्रम में लगाएँ। उन्हें उसी क्रम में आज़माएँ। अगर किसी एज के दोनों सिरे अलग हिस्सों में हैं, तो उसे ट्री में जोड़ें: दोनों हिस्से एक हो जाते हैं। अगर दोनों सिरे पहले से एक ही हिस्से में हैं, तो एज साइकिल बनाएगा, इसलिए उसे छोड़ दें। n नोड के साथ ट्री n − 1 एज के बाद पूरा हो जाता है, और बाकी एज को देखने की ज़रूरत ही नहीं पड़ती।
एक उदाहरण
ये एज लें: A–B लंबाई 1, B–C 2, A–C 3, C–D 4 और B–D 5। क्रुस्कल A–B जोड़ता है, फिर B–C, जो C को A–B वाले हिस्से से जोड़ता है। अगला A–C है, पर A और C पहले से एक हिस्से में हैं, इसलिए यह साइकिल A–B–C बनाएगा और छोड़ दिया जाता है। C–D, D को जोड़ता है, और अब चारों नोड तीन एज वाला एक ट्री बनाते हैं, जिसकी कुल लंबाई 7 है। सबसे लंबा एज B–D कभी आज़माया भी नहीं जाता।
यूनियन-फ़ाइंड
क्रुस्कल एल्गोरिदम का अकेला मुश्किल सवाल है: क्या ये दोनों नोड पहले से एक ही हिस्से में हैं? यूनियन-फ़ाइंड स्ट्रक्चर इसका जवाब देता है। हर हिस्सा लिंक का एक छोटा ट्री है जो एक प्रतिनिधि की ओर इशारा करता है। find लिंक के सहारे प्रतिनिधि तक पहुँचता है; union एक प्रतिनिधि को दूसरे के नीचे जोड़ता है। पाथ कम्प्रेशन, जो रास्ते में मिले हर नोड को सीधे प्रतिनिधि की ओर कर देता है, और साइज़ के हिसाब से यूनियन लिंक को इतना छोटा रखते हैं कि हर सवाल में लगभग स्थिर समय लगता है।
इतिहास और रफ़्तार
जोसेफ़ क्रुस्कल (Joseph Kruskal) ने यह एल्गोरिदम 1956 में Proceedings of the American Mathematical Society के एक छोटे लेख में प्रकाशित किया। एज को क्रम में लगाना सबसे धीमा हिस्सा है, इसलिए E एज के लिए काम E log E के साथ बढ़ता है। अगर एज पहले से क्रम में हों, या उनकी लंबाइयाँ छोटी पूर्ण संख्याएँ हों, तो यह लगभग लीनियर है।
खुद आज़माएँ
ऐप खोलें और “आगे” दबाएँ। जिन एज को अभी आज़माना है, वे ग्राफ़ के नीचे सूची में हैं, सबसे छोटा पहले। दो हिस्सों को जोड़ने वाला हर एज हरा हो जाता है; साइकिल बनाने वाला हर एज लाल डैश वाली रेखा से बनता है। देखें कि ग्राफ़ के अलग-अलग हिस्सों में कई छोटे टुकड़े कैसे बढ़ते और मिलते हैं, और ध्यान दें कि आखिरी एज अक्सर कभी आज़माए ही नहीं जाते।
अक्सर पूछे जाने वाले प्रश्न
क्रुस्कल एल्गोरिदम एज को क्रम में क्यों लगाता है?
ताकि यह जो भी एज जोड़े, वह दो हिस्सों को अब भी जोड़ने वाला सबसे छोटा एज हो। कट प्रॉपर्टी की वजह से यह ग्रीडी चुनाव हमेशा सुरक्षित है, और छोड़ा गया हर एज उस साइकिल का सबसे लंबा एज है जिसे वह बनाता, इसलिए उसकी कभी ज़रूरत नहीं पड़ती।
डिसजॉइंट-सेट स्ट्रक्चर क्या है?
यूनियन-फ़ाइंड का दूसरा नाम: एक स्ट्रक्चर जो अलग-अलग सेट का संग्रह रखता है, यहाँ बढ़ते फ़ॉरेस्ट के हिस्से, और जल्दी बता सकता है कि कोई एलिमेंट किस सेट में है, और दो सेट को मिला सकता है।
क्या क्रुस्कल एल्गोरिदम बिना जुड़े ग्राफ़ पर काम करता है?
हाँ। यह बस ग्राफ़ के हर जुड़े हिस्से के लिए एक ट्री पर खत्म होता है, यानी मिनिमम स्पैनिंग फ़ॉरेस्ट, क्योंकि कोई भी एज बिना जुड़े हिस्सों को नहीं जोड़ सकता।
क्या क्रुस्कल एल्गोरिदम किसी और काम आता है?
इसे जल्दी रोकने पर, आखिरी हिस्सों के मिलने से पहले, नोड क्लस्टर में बँट जाते हैं, और यही सिंगल-लिंकेज क्लस्टरिंग है। रैंडम एज लंबाई वाले ग्रिड पर इसे चलाने से भूलभुलैया बनती है।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
क्रुस्कल एल्गोरिदम आज़माएँ