क्रुस्कल बनाम प्राइम
कंप्यूटर विज्ञान में, प्राइम और क्रुस्कल के एल्गोरिदम एक लालची एल्गोरिदम हैं जो एक जुड़े हुए भारित अप्रत्यक्ष ग्राफ के लिए न्यूनतम फैले हुए पेड़ को ढूंढते हैं। एक फैला हुआ पेड़ एक ग्राफ का एक सबग्राफ होता है जैसे कि ग्राफ का प्रत्येक नोड एक पथ से जुड़ा होता है, जो एक पेड़ है। प्रत्येक फैले हुए पेड़ का वजन होता है, और सभी फैले हुए पेड़ों की न्यूनतम संभव वजन/लागत न्यूनतम फैले हुए पेड़ (एमएसटी) है।
प्राइम के एल्गोरिदम के बारे में अधिक
एल्गोरिदम को 1930 में चेक गणितज्ञ वोज्टेच जर्निक द्वारा विकसित किया गया था और बाद में 1957 में कंप्यूटर वैज्ञानिक रॉबर्ट सी. प्रिम द्वारा स्वतंत्र रूप से विकसित किया गया था। 1959 में एड्सगर डिजस्ट्रा द्वारा इसे फिर से खोजा गया था। एल्गोरिथ्म को तीन प्रमुख चरणों में कहा जा सकता है;
एन नोड्स के साथ जुड़े ग्राफ और प्रत्येक किनारे के संबंधित वजन को देखते हुए, 1. ग्राफ से एक मनमाना नोड चुनें और इसे ट्री टी में जोड़ें (जो पहला नोड होगा)
2. पेड़ में नोड्स से जुड़े प्रत्येक किनारे के वजन पर विचार करें और न्यूनतम का चयन करें। पेड़ T के दूसरे छोर पर किनारे और नोड को जोड़ें और किनारे को ग्राफ़ से हटा दें। (यदि दो या अधिक न्यूनतम मौजूद हैं तो कोई भी चुनें)
3. चरण 2 दोहराएँ, जब तक कि n-1 किनारों को ट्री में न जोड़ दिया जाए।
इस पद्धति में, पेड़ एक एकल मनमाना नोड से शुरू होता है और प्रत्येक चक्र के साथ उस नोड से आगे बढ़ता है। इसलिए, एल्गोरिथम के ठीक से काम करने के लिए, ग्राफ़ को एक कनेक्टेड ग्राफ़ होना चाहिए। प्राइम के एल्गोरिथ्म के मूल रूप में O(V2) की समय जटिलता है।
क्रुस्कल के एल्गोरिथम के बारे में अधिक
जोसफ क्रस्कल द्वारा विकसित एल्गोरिथम 1956 में अमेरिकन मैथमैटिकल सोसाइटी की कार्यवाही में दिखाई दिया। क्रुस्कल के एल्गोरिथ्म को तीन सरल चरणों में भी व्यक्त किया जा सकता है।
एन नोड्स और प्रत्येक किनारे के संबंधित वजन के साथ ग्राफ को देखते हुए, 1. पूरे ग्राफ के कम से कम वजन वाले चाप का चयन करें और पेड़ में जोड़ें और ग्राफ से हटा दें।
2. शेष में से कम से कम भारित किनारे का चयन करें, इस तरह से कि एक चक्र न बने। किनारे को पेड़ में जोड़ें और ग्राफ़ से हटाएं। (यदि दो या अधिक न्यूनतम मौजूद हैं तो कोई भी चुनें)
3. चरण 2 में प्रक्रिया को दोहराएं।
इस पद्धति में, एल्गोरिथ्म कम से कम भारित किनारे से शुरू होता है और प्रत्येक चक्र में प्रत्येक किनारे का चयन करना जारी रखता है। इसलिए, एल्गोरिथम में ग्राफ को जोड़ने की आवश्यकता नहीं है। क्रुस्कल के एल्गोरिथ्म में O(logV) की समय जटिलता है
क्रुस्कल और प्राइम के एल्गोरिथम में क्या अंतर है?
• प्राइम का एल्गोरिथम एक नोड से आरंभ होता है, जबकि क्रुस्कल का एल्गोरिथम एक किनारे से आरंभ होता है।
• प्राइम के एल्गोरिदम एक नोड से दूसरे नोड तक फैले हुए हैं जबकि क्रुस्कल के एल्गोरिदम किनारों का चयन इस तरह से करते हैं कि किनारे की स्थिति अंतिम चरण पर आधारित नहीं है।
• प्राइम के एल्गोरिदम में, ग्राफ़ एक कनेक्टेड ग्राफ़ होना चाहिए, जबकि क्रुस्कल डिस्कनेक्ट किए गए ग्राफ़ पर भी कार्य कर सकता है।
• प्राइम के एल्गोरिथ्म में O(V2) की समय जटिलता है, और क्रुस्कल की समय जटिलता O(logV) है।
