मिनिमम स्पैनिंग ट्री
1926 में, ओताकार बोरुव्का (Otakar Borůvka) से दक्षिणी मोराविया के बिजली नेटवर्क की योजना जितना हो सके उतने सस्ते में बनाने को कहा गया। उनका सवाल, कि लाइन की सबसे कम कुल लंबाई से हर जगह को कैसे जोड़ा जाए, मिनिमम स्पैनिंग ट्री की समस्या है, और इसके कुछ जवाब पूरे कंप्यूटर साइंस में सबसे सरल और सुंदर हैं।
समस्या
एक कनेक्टेड ग्राफ़ लें जिसके एज की लंबाई, या लागत, हो। स्पैनिंग ट्री एज का वह समूह है जो सभी नोड को जोड़ता है और जिसमें कोई साइकिल नहीं होती; n नोड होने पर इसमें हमेशा ठीक n − 1 एज होते हैं, क्योंकि हर एज एक और नोड को जोड़ता है। सभी स्पैनिंग ट्री में से, मिनिमम स्पैनिंग ट्री की कुल लंबाई सबसे कम होती है। किसी ग्राफ़ में बहुत ज़्यादा स्पैनिंग ट्री हो सकते हैं, लेकिन सभी को आज़माने की ज़रूरत नहीं है।
ग्रीडी तरीका क्यों काम करता है
नोड को किसी भी तरह दो समूहों में बाँटें। समूहों के बीच से गुज़रने वाला सबसे छोटा एज हमेशा किसी न किसी मिनिमम स्पैनिंग ट्री का हिस्सा होता है: अगर कोई ट्री उसकी जगह कोई लंबा पार करने वाला एज इस्तेमाल करता, तो उसे छोटे एज से बदलने पर वही नोड कम लागत में जुड़ जाते। यह कट प्रॉपर्टी है। सिक्के का दूसरा पहलू साइकिल प्रॉपर्टी है: किसी भी साइकिल का सबसे लंबा एज कभी ज़रूरी नहीं होता। नीचे के दोनों एल्गोरिदम बस इन्हीं नियमों को लागू करते रहते हैं।
एक उदाहरण
ये एज लें: A–B लंबाई 1, B–C 2, A–C 3, C–D 4 और B–D 5। क्रुस्कल एल्गोरिदम A–B लेता है, फिर B–C, फिर A–C को छोड़ता है, क्योंकि A और C पहले से जुड़े हैं और यह साइकिल बनाएगा, फिर C–D लेता है। ट्री में चार नोड के लिए तीन एज हैं, इसलिए यह पूरा हो गया, कुल लंबाई 7 के साथ, और B–D को देखा तक नहीं गया। A से शुरू होने वाला प्रिम एल्गोरिदम पहले A–B से B जोड़ता है; C तक के रास्ते के रूप में B का एज B–C (2), A–C (3) से बेहतर है, इसलिए C, B–C से जुड़ता है; C का एज C–D (4), B–D (5) से बेहतर है, इसलिए D, C–D से जुड़ता है। वही ट्री, वही 7।
क्रुस्कल, प्रिम और बोरुव्का
क्रुस्कल एल्गोरिदम, जिसे जोसेफ़ क्रुस्कल (Joseph Kruskal) ने 1956 में प्रकाशित किया, एज को क्रम में लगाता है और एक ही हिस्से के अंदर के एज छोड़ने के लिए यूनियन-फ़ाइंड स्ट्रक्चर का इस्तेमाल करता है, इसलिए इसका काम E log E के साथ बढ़ता है। प्रिम एल्गोरिदम को सबसे पहले वोयतेख़ यार्निक (Vojtěch Jarník) ने 1930 में बताया था, और 1957 में रॉबर्ट प्रिम (Robert Prim) और 1959 में एड्सगर डाइक्स्ट्रा (Edsger Dijkstra) ने इसे दोबारा खोजा; बाइनरी हीप के साथ इसका काम E log V के साथ बढ़ता है, और सादे ऐरे के साथ V² के साथ, जो डेंस ग्राफ़ के लिए अच्छा है। बोरुव्का का 1926 का एल्गोरिदम हर हिस्से को एक ही समय में अपना सबसे छोटा बाहर जाने वाला एज लेने देता है, जो पैरेलल कंप्यूटरों के लिए ठीक है।
उपयोग
मिनिमम स्पैनिंग ट्री से केबल, पाइप और सड़कों के सस्ते नेटवर्क डिज़ाइन किए जाते हैं। ये डेटा को क्लस्टर में बाँटते हैं: ट्री के सबसे लंबे एज हटा दें, और जो हिस्से बचें वही क्लस्टर हैं। जब दूरियाँ त्रिभुज नियम मानती हैं, तो ये ट्रैवलिंग सेल्समैन समस्या के लिए जल्दी एक ऐसा टूर देते हैं जो सबसे अच्छे टूर से ज़्यादा से ज़्यादा दोगुना लंबा होता है। और रैंडम एज लंबाई वाले ग्रिड पर क्रुस्कल या प्रिम एल्गोरिदम चलाना भूलभुलैया बनाने का एक क्लासिक तरीका है।
इसे आज़माएँ
ऐप खोलें, क्रुस्कल या प्रिम चुनें, और “आगे” दबाएँ। क्रुस्कल में, जिन एज को अभी आज़माना है, वे ग्राफ़ के नीचे सबसे छोटे से सबसे लंबे तक सूची में हैं; जो एज साइकिल बनाएँगे, वे लाल डैश वाली रेखा में दिखते हैं। प्रिम में, जुड़ने का इंतज़ार कर रहे नोड अपने सबसे अच्छे एज की लंबाई के साथ सूची में हैं, और वह एज डैश वाली रेखा में दिखता है। दोनों को एक ही ग्राफ़ पर चलाएँ और तुलना करें: क्रम अलग है, लेकिन कुल लंबाई हमेशा वही रहती है।
अक्सर पूछे जाने वाले प्रश्न
स्पैनिंग ट्री में कितने एज होते हैं?
नोड की संख्या से ठीक एक कम। इससे कम एज हर नोड को नहीं जोड़ सकते, और एक भी ज़्यादा एज हमेशा साइकिल बनाएगा।
क्रुस्कल और प्रिम में कौन तेज़ है?
एज को क्रम में लगाने वाला क्रुस्कल एल्गोरिदम आम तौर पर ज़्यादा सरल है और कम एज वाले स्पार्स ग्राफ़ पर तेज़ है। हीप वाला प्रिम एल्गोरिदम डेंस ग्राफ़ पर अच्छा काम करता है, और सादे ऐरे के साथ इसे लगभग V² चरण लगते हैं, चाहे कितने भी एज हों।
यूनियन-फ़ाइंड क्या है?
एक डेटा स्ट्रक्चर जो याद रखता है कि कौन-से नोड एक ही हिस्से में हैं। यह “क्या ये दोनों जुड़े हैं?” का जवाब देता है और दो हिस्सों को लगभग तुरंत मिला देता है, और क्रुस्कल एल्गोरिदम को हर एज के लिए ठीक इसी की ज़रूरत होती है।
क्या मिनिमम स्पैनिंग ट्री डायरेक्टेड ग्राफ़ पर काम करता है?
सीधे तौर पर नहीं। एक-तरफ़ा एज वाले ग्राफ़ के लिए, इससे मिलती-जुलती समस्या मिनिमम स्पैनिंग आर्बोरेसेंस है, जिसे Chu–Liu/Edmonds एल्गोरिदम से हल किया जाता है।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
मिनिमम स्पैनिंग ट्री बनाएँ