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

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

मिनिमम स्पैनिंग ट्री के बारे में और

मिनिमम स्पैनिंग ट्री

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

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

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

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

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

प्रिम एल्गोरिदम

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

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

मिनिमम स्पैनिंग ट्री क्या है?

ऐसे कनेक्टेड ग्राफ़ में जिसके एज की लंबाई होती है, स्पैनिंग ट्री एज का वह समूह है जो बिना किसी साइकिल के सभी नोड को जोड़ता है; n नोड होने पर इसमें हमेशा n − 1 एज होते हैं। मिनिमम स्पैनिंग ट्री वह स्पैनिंग ट्री है जिसकी कुल लंबाई जितनी हो सके उतनी कम हो।

क्रुस्कल और प्रिम एल्गोरिदम में क्या फ़र्क है?

क्रुस्कल एल्गोरिदम पूरे ग्राफ़ के एज को सबसे छोटे से सबसे लंबे तक देखता है और अलग-अलग हिस्सों को जोड़कर एक ट्री बनाता है। प्रिम एल्गोरिदम शुरुआत से एक ही ट्री बढ़ाता है, और हमेशा उससे बाहर जाने वाला सबसे छोटा एज जोड़ता है। दोनों ग्रीडी हैं और एक ही कुल लंबाई वाला ट्री खोजते हैं; क्रुस्कल स्पार्स ग्राफ़ के लिए ठीक है, प्रिम डेंस ग्राफ़ के लिए।

क्या मिनिमम स्पैनिंग ट्री एक ही होता है?

जब सभी एज की लंबाई अलग-अलग हो, तो हाँ। जब कुछ लंबाइयाँ बराबर हों, तो एक ही सबसे कम कुल वाले कई ट्री हो सकते हैं, और बराबरी को कैसे सुलझाया जाता है, इसके हिसाब से एल्गोरिदम अलग-अलग ट्री चुन सकते हैं।

क्या मिनिमम स्पैनिंग ट्री और सबसे छोटे रास्ते एक ही चीज़ हैं?

नहीं। मिनिमम स्पैनिंग ट्री सभी एज की कुल लंबाई कम रखता है, लेकिन ट्री में दो नोड के बीच का रास्ता उनके सबसे छोटे रास्ते से कहीं लंबा हो सकता है। सबसे छोटे रास्तों के लिए डाइक्स्ट्रा एल्गोरिदम का इस्तेमाल करें।

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

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

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

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

एडिटर पर जाएँ