इस पोस्ट में, हम प्रिम और क्रुस्कल के एल्गोरिदम के बीच अंतर को समझेंगे।
न्यूनतम स्पैनिंग ट्री (MST) के लिए क्रुस्कल का एल्गोरिदम
- जब एक कनेक्टेड और अनडायरेक्टेड ग्राफ दिया जाता है, तो ऐसे ग्राफ का स्पैनिंग ट्री वह सबग्राफ है जो एक ट्री है जो सभी वर्टेक्स को जोड़ता है।
- एक सिंगल ग्राफ के कई स्पैनिंग ट्री हो सकते हैं।
- एक वेटेड, कनेक्टेड और अनडायरेक्टेड ग्राफ के लिए न्यूनतम स्पैनिंग ट्री (MST) (जिसे न्यूनतम वजन स्पैनिंग ट्री भी कहा जाता है) एक स्पैनिंग ट्री है जिसका वजन हर दूसरे स्पैनिंग ट्री के वजन से कम या बराबर होता है।
- स्पैनिंग ट्री का वजन स्पैनिंग ट्री के हर एज से जुड़े वजन को जोड़कर निर्धारित किया जाता है।
- न्यूनतम स्पैनिंग ट्री को ग्राफ में न्यूनतम वजन वाले वर्टेक्स से बनाया जा सकता है।
- एक नोड को केवल एक बार पार किया जाता है।
- यह स्पार्स ग्राफ में तेजी से चलता है।
- समय जटिलता O(E log V) है, जहां V वर्टेक्स की संख्या है।
- यह डिस्कनेक्टेड कंपोनेंट्स के साथ भी काम कर सकता है।
क्रुस्कल के एल्गोरिदम का उपयोग करके MST खोजने के चरण:
- एजेस को उनके संबंधित वजन के आरोही क्रम में सॉर्ट करें।
- सबसे छोटा एज चुनें।
- चेक करें कि क्या यह उस बिंदु तक बने स्पैनिंग-ट्री के साथ साइकिल बनाता है।
- यदि साइकिल नहीं बनी है, तो इस एज को शामिल करना होगा।
- अन्यथा, इसे छोड़ दिया जा सकता है।
- चरण 2,3,4 को तब तक दोहराएं जब तक स्पैनिंग ट्री में V-1 एज न हों।
न्यूनतम स्पैनिंग ट्री (MST) के लिए प्रिम का एल्गोरिदम
- यह क्रुस्कल के एल्गोरिदम के समान है, यानी यह एक ग्रीडी एल्गोरिदम है।
- यह एक खाली स्पैनिंग ट्री से शुरू होता है। वर्टेक्स के दो सेट बनाए रखे जाते हैं।
- पहला सेट उन वर्टेक्स को समाहित करेगा जो पहले से MST में शामिल हैं, जबकि दूसरा सेट उन वर्टेक्स को समाहित करता है जिन्हें अभी तक शामिल नहीं किया गया है।
- हर चरण में, एल्गोरिदम उन सभी एजेस पर विचार करता है जो दोनों सेट्स को जोड़ते हैं। यह इन एजेस में से न्यूनतम वजन वाली एज चुनता है।
- इस चरण के बाद, एल्गोरिदम MST वाले सेट के एज के दूसरे एंडपॉइंट पर जाता है।
- न्यूनतम स्पैनिंग ट्री को ग्राफ में किसी भी वर्टेक्स से बनाया जा सकता है।
- न्यूनतम दूरी मान प्राप्त करने के लिए एक नोड को कई बार पार किया जाता है।
- इसकी समय जटिलता O(V²) है, जहां V वर्टेक्स की संख्या है। फाइबोनैचि हीप्स का उपयोग करके इस समय जटिलता को O(E + log V) तक बढ़ाया जा सकता है।
- यह डेंस ग्राफ में तेजी से चलता है।
- यह कनेक्टेड कंपोनेंट्स देता है, और केवल कनेक्टेड ग्राफ के साथ काम करता है।
प्रिम के एल्गोरिदम का उपयोग करके MST खोजने के चरण:
- एक mstSet बनाया जाता है, जो उन वर्टेक्स को ट्रैक करता है जो पहले से MST में शामिल हैं।
- इनपुट ग्राफ के सभी वर्टेक्स को एक की वैल्यू असाइन की जाती है।
- की वैल्यूज को प्रारंभ में 'INFINITE' असाइन किया जाता है।
- पहले वर्टेक्स को की वैल्यू 0 असाइन की जाती है ताकि इसे पहले चुना जा सके।
- जब mstSet में सभी वर्टेक्स शामिल नहीं होते, तो नीचे के चरणों का पालन किया जाता है।
- एक वर्टेक्स 'u' चुना जाता है जो mstSet में मौजूद नहीं है और जिसकी न्यूनतम की वैल्यू है।
- यह 'u' अब mstSet में शामिल है।
- 'u' के सभी आसन्न वर्टेक्स की की वैल्यू अपडेट की जाती है।
- यह सभी आसन्न वर्टेक्स के माध्यम से पुनरावृति करके किया जा सकता है।
- हर आसन्न वर्टेक्स 'v' के लिए, यदि एज 'u'-'v' का वजन 'v' की पिछली की वैल्यू से कम है, तो की वैल्यू को 'u-v' के वजन के रूप में अपडेट किया जाता है।
