प्राइम और क्रुस्कल के एल्गोरिदम के बीच अंतर

इस पोस्ट में, हम प्राइम और क्रुस्कल के एल्गोरिदम के बीच के अंतर को समझेंगे।

मिनिनम स्पैनिंग ट्री (MST) के लिए क्रुस्कल का एल्गोरिथम

जब एक जुड़ा हुआ और अप्रत्यक्ष ग्राफ दिया जाता है, तो ऐसे ग्राफ का एक फैला हुआ पेड़ सबग्राफ होता है जो एक ऐसा पेड़ होता है जो सभी शीर्षों को जोड़ता है।
एक ग्राफ़ में कई फैले हुए पेड़ हो सकते हैं।
एक भारित, जुड़े और अप्रत्यक्ष ग्राफ के लिए न्यूनतम फैले हुए पेड़ (एमएसटी) (जिसे न्यूनतम वजन फैले हुए पेड़ के रूप में भी जाना जाता है) एक फैले हुए पेड़ है जिसका वजन हर दूसरे फैले पेड़ के वजन से कम या उसके बराबर होता है।
एक फैले हुए पेड़ का वजन फैले हुए पेड़ के हर किनारे से जुड़े वजन को जोड़कर निर्धारित किया जाता है।
न्यूनतम फैले हुए पेड़ को उस शीर्ष से बनाया जा सकता है जिसका ग्राफ़ में न्यूनतम भार है।
एक नोड को केवल एक बार ट्रेस किया जाता है।
यह विरल ग्राफ़ में तेज़ी से चलता है।
समय जटिलता O(E log V) है, जहां V शीर्षों की संख्या है।
यह डिस्कनेक्ट किए गए घटकों के साथ भी काम कर सकता है।

कृस्कल के एल्गोरिथम का उपयोग करके एमएसटी खोजने के चरण:

किनारों को उनके संबंधित भार के आरोही क्रम में क्रमबद्ध करें।
सबसे छोटा किनारा चुनें।
यह देखने के लिए जांचें कि क्या यह उस समय तक बने स्पैनिंग-ट्री के साथ एक चक्र बनाता है।
यदि चक्र नहीं बना है, तो इस किनारे को शामिल करना होगा।
अन्यथा, इसे छोड़ा जा सकता है।
चरण 2,3,4 तब तक दोहराए जाते हैं जब तक कि फैले हुए पेड़ में V-1 किनारे न हों।

प्राइम का एल्गोरिथम मिनिनम स्पैनिंग ट्री (MST)

यह क्रुस्कल के एल्गोरिदम के समान है, यानी यह एक लालची एल्गोरिदम है।
यह एक खाली फैले हुए पेड़ से शुरू होता है। शीर्षों के दो सेट बनाए हुए हैं।
पहले सेट में वे कोने होंगे जो पहले से ही MST में शामिल हैं, जबकि दूसरे सेट में वे कोने हैं जिन्हें अभी तक शामिल नहीं किया गया है।
हर कदम पर, एल्गोरिथ्म उन सभी किनारों पर विचार करता है जो दो सेटों को जोड़ते हैं। इसके बाद यह इन किनारों के बीच न्यूनतम वजन का किनारा चुनता है।
इस चरण के बाद, एल्गोरिथम सेट के किनारे के दूसरे छोर पर चला जाता है जिसमें MST होता है।
न्यूनतम फैले हुए पेड़ को ग्राफ़ के किसी भी शीर्ष से बनाया जा सकता है।
न्यूनतम दूरी मान प्राप्त करने के लिए एक नोड को कई बार यात्रा की जाती है।
इसमें O(V2) की समय जटिलता है, जहां V शीर्षों की संख्या है। इस बार जटिलता को फाइबोनैचि हीप्स का उपयोग करके O(E + log V) तक बढ़ाया जा सकता है।
यह घने ग्राफ़ में तेज़ी से चलता है।
यह कनेक्टेड कंपोनेंट्स देता है, और केवल कनेक्टेड ग्राफ़ के साथ काम करता है।

प्राइम के एल्गोरिथम का उपयोग करके एमएसटी खोजने के चरण:

एक mstSet बनाया गया है, जो उन शीर्षों का ट्रैक रखता है जो पहले से ही MST में शामिल हैं।
इनपुट ग्राफ़ के सभी शीर्षों को एक मुख्य मान असाइन किया जाता है।
प्रमुख मान प्रारंभ में 'अनंत' के रूप में निर्दिष्ट किए गए हैं।
कुंजी मान 0 को पहले शीर्ष को सौंपा गया है ताकि इसे पहले चुना जा सके।
जब mstSet में सभी शीर्ष शामिल नहीं होते हैं, तो नीचे दिए गए चरणों का पालन किया जाता है।
- एक शीर्ष 'u' चुना गया है जो mstSet में मौजूद नहीं है और न्यूनतम कुंजी मान भी है।
- यह 'यू' अब mstSet में शामिल है।
- 'u' के सभी निकटवर्ती शीर्षों का मुख्य मान अपडेट किया जाता है।
- यह सभी आसन्न शीर्षों के माध्यम से पुनरावृति करके किया जा सकता है।
- प्रत्येक आसन्न शीर्ष 'v' के लिए, यदि किनारे 'u'-'v' का भार 'v' के पिछले कुंजी मान से कम है, तो कुंजी मान को 'u-v' के भार के रूप में अद्यतन किया जाता है '।