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

सोचिए कि आप बिजलीघर से केबल बिछा रहे हैं: पहले सबसे पास वाले शहर को जोड़ते हैं, फिर उस शहर को जो पहले से जुड़ी किसी भी जगह के सबसे पास हो, और इसी तरह आगे। यही प्रिम एल्गोरिदम है, और इसका नतीजा हमेशा सबसे सस्ता नेटवर्क होता है।

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

मूल विचार

मिनिमम स्पैनिंग ट्री वेटेड ग्राफ़ के हर नोड को सबसे कम संभव कुल एज लंबाई से जोड़ता है। प्रिम एल्गोरिदम इसे शुरुआत से बाहर की ओर एक ट्री बढ़ाकर बनाता है। ट्री कभी टुकड़ों में नहीं बँटता: हर चरण में ठीक एक नया नोड, ट्री से बाहर जाने वाले सबसे छोटे एज से, उसमें जुड़ता है।

चरण-दर-चरण

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

एक उदाहरण

ये एज लें: A–B लंबाई 1, B–C 2, A–C 3, C–D 4 और B–D 5, और A से शुरू करें। A के एज B को सबसे अच्छा एज 1 और C को 3 देते हैं। B सबसे पास है, इसलिए वह A–B से जुड़ता है; उसके एज C को सुधारकर 2 कर देते हैं और D को 5 देते हैं। C, B–C से जुड़ता है, और उसका एज C–D, D को सुधारकर 4 कर देता है। आखिर में D, C–D से जुड़ता है। ट्री A–B, B–C, C–D की कुल लंबाई 1 + 2 + 4 = 7 है।

यह सही क्यों है

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

इतिहास और रफ़्तार

चेक गणितज्ञ वोयतेख़ यार्निक (Vojtěch Jarník) ने यह एल्गोरिदम 1930 में प्रकाशित किया। रॉबर्ट प्रिम (Robert Prim) ने 1957 में बेल लैब्स (Bell Labs) में इसे दोबारा खोजा, और एड्सगर डाइक्स्ट्रा (Edsger Dijkstra) ने 1959 में फिर से। इंतज़ार कर रहे नोड को बाइनरी हीप में रखने पर, V नोड और E एज के लिए काम E log V के साथ बढ़ता है; सादे ऐरे के साथ यह लगभग V² है, जो तब बेहतर है जब लगभग हर जोड़ी नोड जुड़ी हो। फ़िबोनाची हीप के साथ यह E + V log V है।

खुद आज़माएँ

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

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

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

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

क्या प्रिम एल्गोरिदम नेगेटिव एज लंबाई के साथ काम करता है?

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

अगर ग्राफ़ जुड़ा हुआ न हो तो?

तब प्रिम एल्गोरिदम उन सभी नोड तक पहुँचकर रुक जाता है जहाँ तक पहुँच सकता है: यह सिर्फ़ शुरुआत वाले हिस्से का मिनिमम स्पैनिंग ट्री देता है। जिस नोड तक अभी नहीं पहुँचे, वहाँ से इसे फिर चलाने पर मिनिमम स्पैनिंग फ़ॉरेस्ट मिलता है।

प्रिम या क्रुस्कल, कौन-सा एल्गोरिदम बेहतर है?

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

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

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

प्रिम एल्गोरिदम आज़माएँ