- मौजूदा
- ट्री में
- ट्री के पास
- अब तक का सबसे अच्छा एज
प्रिम एल्गोरिदम
प्रिम एल्गोरिदम मिनिमम स्पैनिंग ट्री बनाता है, यानी एज का वह सबसे सस्ता समूह जो हर नोड को जोड़ता है, और यह शुरुआत से एक ही ट्री बढ़ाकर करता है। हर चरण में यह वह नोड जोड़ता है जिस तक ट्री से सबसे छोटे एज से पहुँचा जा सके। किसी नोड पर क्लिक करके वहीं से शुरू करें और चरण-दर-चरण इंतज़ार कर रहे नोड, उनके सबसे अच्छे एज और बढ़ता ट्री देखें। ट्री को बढ़ते देखने के लिए “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। किसी नोड को शुरुआत बनाने के लिए उस पर क्लिक करें: ट्री वहीं से बढ़ता है। हर एज पर लिखी संख्या उसकी लंबाई है। ग्राफ़ के नीचे वे नोड हैं जो जुड़ने का इंतज़ार कर रहे हैं, हर एक के साथ ट्री तक के उसके सबसे अच्छे एज की लंबाई, और वह एज डैश वाली रेखा से बना होता है। “नया ग्राफ़” दूसरा ग्राफ़ बनाता है; उसमें कितने नोड और एज हों, यह चुनें। बोर्ड चुना होने पर, ऐरो कुंजियाँ एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।
यह कैसे काम करता है
- किसी नोड को शुरुआत बनाने के लिए उस पर क्लिक करें: ट्री वहीं से बढ़ता है।
- “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” का इस्तेमाल करें। कहीं भी जाने के लिए चरण स्लाइडर खींचें।
- ग्राफ़ के नीचे इंतज़ार कर रहे नोड देखें, हर एक के साथ ट्री तक का उसका सबसे अच्छा एज। “नया ग्राफ़” आज़माने के लिए दूसरा ग्राफ़ बनाता है।
प्रिम एल्गोरिदम कैसे काम करता है
एक नोड वाले ट्री से शुरू करें। ट्री के बाहर का हर नोड ट्री तक का अपना सबसे छोटा एज याद रखता है, अगर उसका कोई हो। बार-बार वह नोड लें जिसका एज सबसे छोटा हो, उसे और उस एज को ट्री में जोड़ें, और उसके एज देखें: अगर कोई एज किसी पड़ोसी के अब तक के सबसे अच्छे एज से छोटा है, तो वह उस पड़ोसी का सबसे अच्छा एज बन जाता है। जब हर नोड जुड़ जाए, तो ट्री में नोड से एक कम एज होते हैं, और उसकी कुल लंबाई सबसे कम होती है।
प्रिम और डाइक्स्ट्रा
प्रिम एल्गोरिदम और डाइक्स्ट्रा एल्गोरिदम लगभग एक जैसे दिखते हैं: दोनों शुरुआत से एक इलाका बढ़ाते हैं और इंतज़ार कर रहे नोड को प्रायोरिटी क्यू में रखते हैं। फ़र्क क्यू में रखी संख्या का है। डाइक्स्ट्रा हर नोड की शुरुआत से पूरी दूरी रखता है; प्रिम सिर्फ़ ट्री तक के उसके एक सबसे अच्छे एज की लंबाई रखता है। इसलिए डाइक्स्ट्रा सबसे छोटे रास्तों का ट्री बनाता है, और प्रिम सबसे कम कुल लंबाई वाला ट्री, और ये दोनों ट्री अक्सर अलग होते हैं।
अक्सर पूछे जाने वाले प्रश्न
प्रिम एल्गोरिदम क्या है?
एक ग्रीडी एल्गोरिदम जो शुरुआती नोड से एक ट्री बढ़ाकर वेटेड ग्राफ़ का मिनिमम स्पैनिंग ट्री बनाता है, और हमेशा वह सबसे छोटा एज जोड़ता है जो ट्री को उसके बाहर के किसी नोड से जोड़ता है।
क्या शुरुआती नोड से फ़र्क पड़ता है?
सिर्फ़ क्रम पर: किसी भी शुरुआत से प्रिम एल्गोरिदम उसी सबसे कम कुल लंबाई वाले स्पैनिंग ट्री पर खत्म होता है। जब कुछ एज की लंबाई बराबर हो, तो ट्री खुद अलग हो सकता है।
प्रिम एल्गोरिदम किसने बनाया?
वोयतेख़ यार्निक (Vojtěch Jarník) ने इसे सबसे पहले 1930 में बताया। रॉबर्ट प्रिम (Robert Prim) ने 1957 में और एड्सगर डाइक्स्ट्रा (Edsger Dijkstra) ने 1959 में इसे दोबारा खोजा, इसलिए इसे यार्निक एल्गोरिदम या प्रिम–यार्निक एल्गोरिदम भी कहते हैं।
प्रिम एल्गोरिदम कितना तेज़ है?
बाइनरी हीप के साथ, V नोड और E एज के लिए इसका काम E log V के साथ बढ़ता है। हीप की जगह सादे ऐरे के साथ इसमें लगभग V² चरण लगते हैं, जो डेंस ग्राफ़ के लिए बेहतर है, जहाँ लगभग हर जोड़ी नोड जुड़ी होती है।
क्या मेरा ग्राफ़ कहीं भेजा जाता है?
नहीं। ग्राफ़ और ट्री आपके ब्राउज़र में ही बनते हैं, और आपकी पिछली सेटिंग इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ