जावास्क्रिप्ट में क्रुस्कल का एल्गोरिदम

क्रुस्कल का एल्गोरिथम एक लालची एल्गोरिथम है जो इस प्रकार काम करता है -

1. यह ग्राफ़ में सभी किनारों का एक सेट बनाता है।

2. जबकि उपरोक्त सेट खाली नहीं है और सभी शीर्षों को कवर नहीं किया गया है,

यह इस सेट से न्यूनतम वजन बढ़त को हटा देता है
यह जांचता है कि क्या यह किनारा एक चक्र बना रहा है या सिर्फ 2 पेड़ों को जोड़ रहा है। यदि यह एक चक्र बनाता है, तो हम इस किनारे को छोड़ देते हैं, अन्यथा हम इसे अपने पेड़ में जोड़ देते हैं।

3. जब उपरोक्त प्रसंस्करण पूरा हो जाता है, तो हमारे पास न्यूनतम फैले हुए पेड़ होते हैं।

इस एल्गोरिथम को लागू करने के लिए, हमें 2 और डेटा संरचनाओं की आवश्यकता है।

सबसे पहले, हमें एक प्राथमिकता कतार की आवश्यकता होती है जिसका उपयोग हम किनारों को क्रमबद्ध क्रम में रखने के लिए कर सकते हैं और प्रत्येक पुनरावृत्ति पर अपनी आवश्यक बढ़त प्राप्त कर सकते हैं।

इसके बाद, हमें एक अलग सेट डेटा संरचना की आवश्यकता है। एक असंबद्ध-सेट डेटा संरचना (जिसे संघ-ढूंढें डेटा संरचना या मर्ज-ढूंढें सेट भी कहा जाता है) एक डेटा संरचना है जो कई अलग-अलग (गैर-अतिव्यापी) सबसेट में विभाजित तत्वों के एक सेट को ट्रैक करती है। जब भी हम किसी पेड़ में एक नया नोड जोड़ते हैं, तो हम जांच करेंगे कि क्या वे पहले से जुड़े हुए हैं। यदि हाँ, तो हमारे पास एक चक्र है। यदि नहीं, तो हम किनारे के दोनों शीर्षों का मिलन करेंगे। यह उन्हें एक ही सबसेट में जोड़ देगा।

आइए हम UnionFind या DisjointSet डेटा संरचना के कार्यान्वयन को देखें &minsu;

उदाहरण

class UnionFind { कंस्ट्रक्टर (एलिमेंट्स) {// डिस्कनेक्ट किए गए कंपोनेंट्स की संख्या this.count =element.length; // जुड़े हुए घटकों का ट्रैक रखें this.parent ={}; // डेटा संरचना को इस तरह से प्रारंभ करें कि सभी // तत्वों के पास माता-पिता तत्व हों। प्रत्येक के लिए (ई => (यह। माता-पिता [ई] =ई)); } संघ (ए, बी) { रूट ए =यह। ढूंढें (ए); चलो rootB =this.find(b); // रूट समान हैं इसलिए ये पहले से ही जुड़े हुए हैं। अगर (रूटए ===रूटबी) वापसी; // हमेशा छोटे रूट वाले तत्व को पैरेंट बनाएं। अगर (रूट ए <रूटबी) { अगर (यह माता-पिता [बी]! =बी) यह संघ (यह माता-पिता [बी], ए); यह। माता-पिता [बी] =यह। माता-पिता [ए]; } और { अगर (यह। माता-पिता [ए]! =ए) यह संघ (यह माता-पिता [ए], बी); यह। माता-पिता [ए] =यह। माता-पिता [बी]; } } // एक नोड के अंतिम पैरेंट को ढूंढता है (ए) { जबकि (यह। माता-पिता [ए]! ==ए) {ए =यह। माता-पिता [ए]; } वापसी एक; } // जुड़े हुए 2 नोड्स की कनेक्टिविटी की जांच करता है (ए, बी) { इसे लौटाएं। ढूंढें (ए) ===यह। ढूंढें (बी); }} 
 आप इसका उपयोग करके परीक्षण कर सकते हैं -
 उदाहरण
 चलो uf =new UnionFind(["A", "B", "C", "D", "E"]);uf.union("A", "B"); uf.union("A", "C");uf.union("C", "D");console.log(uf.connected("B", "E"));console.log(uf. कनेक्टेड ("बी", "डी"));
 आउटपुट
 
 यह आउटपुट देगा -
 गलत सच
 
 आइए अब हम इस डेटा संरचना का उपयोग करते हुए क्रुस्कल के एल्गोरिथम के कार्यान्वयन को देखें -
 उदाहरण
 kruskalsMST() {// ग्राफ़ को प्रारंभ करें जिसमें MST const MST =new Graph() होगा; this.nodes.forEach (नोड => MST.addNode (नोड)); अगर (this.nodes.length ===0) { MST लौटाएं; } // एक प्राथमिकता कतार बनाएं edgeQueue =नई प्राथमिकता कतार (यह। नोड्स। लंबाई * यह। नोड्स। लंबाई); // कतार में सभी किनारों को जोड़ें:के लिए (इस.किनारों में नोड दें) {this.edges[node].forEach(edge => { edgeQueue.enqueue([node, edge.node], edge.weight); } ); } चलो uf =नया UnionFind (this.nodes); // लूप जब तक हम सभी नोड्स का पता नहीं लगाते हैं या कतार खाली है, जबकि (! edgeQueue.isEmpty ()) {// डिस्ट्रक्टिंग लेट नेक्स्टएज =edgeQueue.dequeue (); नोड्स =nextEdge.data दें; वजन होने दें =nextEdge.priority; अगर (! uf.connected (नोड्स [0], नोड्स [1])) { MST.addEdge (नोड्स [0], नोड्स [1], वजन); uf.union (नोड्स [0], नोड्स [1]); } } एमएसटी लौटाएं;}
 
 आप इसका उपयोग करके परीक्षण कर सकते हैं -
 उदाहरण
 चलो g =नया ग्राफ़ ();g.addNode("A");g.addNode("B");g.addNode("C");g.addNode("D");g.addNode ("ई");g.addNode("F");g.addNode("G");g.addEdge("A", "C", 100);g.addEdge("A", "B" , 3);g.addEdge("A", "D", 4);g.addEdge("C", "D", 3);g.addEdge("D", "E", 8);g .addEdge("E", "F", 10);g.addEdge("B", "G", 9);g.addEdge("E", "G", 50);g.kruskalsMST ()। डिस्प्ले ();
 आउटपुट
 
 यह आउटपुट देगा -
 A->B, DB->A, GC->DD->C, A, EE->D, FF->EG->B