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

प्रिम का एल्गोरिदम एक लालची एल्गोरिदम है जो वेटेड अनडायरेक्टेड ग्राफ के लिए न्यूनतम स्पैनिंग ट्री ढूंढता है। यह एजेज का एक सबसेट ढूंढता है जो एक ट्री बनाता है जिसमें हर वर्टेक्स शामिल होता है, जहां ट्री में सभी एजेज का कुल वजन न्यूनतम होता है।

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

प्रिम का एल्गोरिदम कैसे काम करता है?

आइए देखते हैं कि प्रिम का एल्गोरिदम कैसे काम करता है इसका एक चित्रण:

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

2. आउटगोइंग एजेज की जांच करें और कम लागत वाले को चुनें: रूट नोड S चुनने के बाद, हम देखते हैं कि S, A और S, C दो एज हैं जिनका वजन क्रमशः 7 और 8 है। हम एज S, A को चुनते हैं क्योंकि यह दूसरे से कम है।

अब, ट्री S-7-A को एक नोड के रूप में माना जाता है और हम इससे बाहर जाने वाली सभी एजेज की जांच करते हैं। हम सबसे कम लागत वाले को चुनते हैं और इसे ट्री में शामिल करते हैं।

इस चरण के बाद, S-7-A-3-C ट्री बनता है। अब हम फिर से इसे एक नोड के रूप में मानेंगे और सभी एजेज की फिर से जांच करेंगे। हालांकि, हम केवल सबसे कम लागत वाली एज चुनेंगे। इस मामले में, C-3-D नई एज है, जो अन्य एजेज की लागत 8, 6, 4 आदि से कम है।

नोड D को स्पैनिंग ट्री में जोड़ने के बाद, अब हमारे पास इससे बाहर जाने वाली दो एज हैं जिनकी लागत समान है, यानी D-2-T और D-2-B। इस प्रकार, हम उनमें से किसी एक को जोड़ सकते हैं। लेकिन अगला चरण फिर से एज 2 को सबसे कम लागत के रूप में देगा। इसलिए, हम दोनों एजेज शामिल करके स्पैनिंग ट्री दिखा रहे हैं।

अब आइए देखते हैं कि हम इसे अपने कोड में कैसे लागू कर सकते हैं:

उदाहरण

primsMST() {
    // MST रखने वाला ग्राफ इनिशियलाइज़ करें
    const MST = new Graph();
    if (this.nodes.length === 0) {
        return MST;
    }
    // पहले नोड को शुरुआती नोड के रूप में चुनें
    let s = this.nodes[0];
    // प्रायोरिटी क्यू और एक्सप्लोर्ड सेट बनाएं
    let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
    let explored = new Set();
    explored.add(s);
    MST.addNode(s);
    // इस शुरुआती नोड से सभी एजेज को वजन को प्रायोरिटी के रूप में लेकर PQ में जोड़ें
    this.edges[s].forEach(edge => {
        edgeQueue.enqueue([s, edge.node], edge.weight);
    });
    // सबसे छोटी एज लें और उसे नए ग्राफ में जोड़ें
    let currentMinEdge = edgeQueue.dequeue();
    while (!edgeQueue.isEmpty()) {
        // अनएक्सप्लोर्ड नोड वाली एज मिलने तक एज हटाते रहें
        while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
            currentMinEdge = edgeQueue.dequeue();
        }
        let nextNode = currentMinEdge.data[1];
        // फिर से जांचें क्योंकि क्यू अनएक्सप्लोर्ड एलिमेंट दिए बिना खाली हो सकती है
        if (!explored.has(nextNode)) {
            MST.addNode(nextNode);
            MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);
            // फिर से सभी एजेज को PQ में जोड़ें
            this.edges[nextNode].forEach(edge => {
                edgeQueue.enqueue([nextNode, edge.node], edge.weight);
            });
            // इस नोड को एक्सप्लोर्ड मार्क करें
            explored.add(nextNode);
            s = nextNode;
        }
    }
    return MST;
}

आप इसका परीक्षण इस तरह कर सकते हैं:

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
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.primsMST().display();

आउटपुट

इससे निम्न आउटपुट मिलेगा:

A->B, D
B->A, G
D->A, C, E
C->D
E->D, F
G->B
F->E

ध्यान दें कि हमारा प्रारंभिक ग्राफ था:

उदाहरण

/**
 *       A
 *     / | \
 *    C  | B
 *     \ | |
 *      D G
 *      | /
 *      E
 *      |
 *      F */

आउटपुट

हमारा वर्तमान ग्राफ इस तरह दिखता है:

/**
 *       A
 *       |\
 *    C  | B
 *     \ | |
 *      D G
 *      |
 *      E
 *      |
 *      F
 *      * */

हमने सबसे महंगी एजेज को हटा दिया है और अब हमारे पास एक स्पैनिंग ट्री है।