जावास्क्रिप्ट में पूर्ण ग्राफ क्लास

इस कोड में जिन फ़ंक्शन्स को कमेंट किया गया है। आप उन पर भी स्विच कर सकते हैं। हमने क्यू, स्टैक, और प्रायोरिटी क्यू क्लास को अलग-अलग मॉड्यूल में भी स्थानांतरित कर दिया है जिन्हें इम्पोर्ट स्टेटमेंट्स या रिक्वायर कॉल का उपयोग करके इम्पोर्ट किया जा सकता है। यहां ग्राफ क्लास का पूरा कार्यान्वयन है:

उदाहरण

const Queue = require("./Queue");
const Stack = require("./Stack");
const PriorityQueue = require("./PriorityQueue");
class Graph {
    constructor() {
        this.edges = {};
        this.nodes = [];
    }
    addNode(node) {
        this.nodes.push(node);
        this.edges[node] = [];
    }
    addEdge(node1, node2, weight = 1) {
        this.edges[node1].push({ node: node2, weight: weight });
        this.edges[node2].push({ node: node1, weight: weight });
    }
    addDirectedEdge(node1, node2, weight = 1) {
        this.edges[node1].push({ node: node2, weight: weight });
    }
    // addEdge(node1, node2) {
    //     this.edges[node1].push(node2);
    //     this.edges[node2].push(node1);
    // }
    // addDirectedEdge(node1, node2) {
    //     this.edges[node1].push(node2);
    // }
    display() {
        let graph = "";
        this.nodes.forEach(node => {
            graph += node + "->" + this.edges[node].map(n => n.node).join(", ") + "\n";
        });
        console.log(graph);
    }
    BFS(node) {
        let q = new Queue(this.nodes.length);
        let explored = new Set();
        q.enqueue(node);
        explored.add(node);
        while (!q.isEmpty()) {
            let t = q.dequeue();
            console.log(t);
            this.edges[t].filter(n => !explored.has(n)).forEach(n => {
                explored.add(n);
                q.enqueue(n);
            });
        }
    }
    DFS(node) {
        // एक स्टैक बनाएं और इसमें अपना प्रारंभिक नोड जोड़ें
        let s = new Stack(this.nodes.length);
        let explored = new Set();
        s.push(node);
        // पहले नोड को एक्सप्लोर्ड मार्क करें
        explored.add(node);
        // हम तब तक जारी रखेंगे जब तक हमारा स्टैक खाली न हो जाए
        while (!s.isEmpty()) {
            let t = s.pop();
            // स्टैक से निकलने वाले हर एलिमेंट को लॉग करें
            console.log(t);
            // 1. एजेज ऑब्जेक्ट में, हम उन नोड्स को खोजते हैं जिनसे यह नोड सीधे जुड़ा हुआ है।
            // 2. हम उन नोड्स को फ़िल्टर करते हैं जो पहले से एक्सप्लोर्ड हैं।
            // 3. फिर प्रत्येक अनएक्सप्लोर्ड नोड को एक्सप्लोर्ड मार्क करते हैं और इसे स्टैक में पुश करते हैं।
            this.edges[t].filter(n => !explored.has(n)).forEach(n => {
                explored.add(n);
                s.push(n);
            });
        }
    }
    topologicalSortHelper(node, explored, s) {
        explored.add(node);
        this.edges[node].forEach(n => {
            if (!explored.has(n)) {
                this.topologicalSortHelper(n, explored, s);
            }
        });
        s.push(node);
    }
    topologicalSort() {
        // एक स्टैक बनाएं और इसमें अपना प्रारंभिक नोड जोड़ें
        let s = new Stack(this.nodes.length);
        let explored = new Set();
        this.nodes.forEach(node => {
            if (!explored.has(node)) {
                this.topologicalSortHelper(node, explored, s);
            }
        });
        while (!s.isEmpty()) {
            console.log(s.pop());
        }
    }
    BFSShortestPath(n1, n2) {
        let q = new Queue(this.nodes.length);
        let explored = new Set();
        let distances = { n1: 0 };
        q.enqueue(n1);
        explored.add(n1);
        while (!q.isEmpty()) {
            let t = q.dequeue();
            this.edges[t].filter(n => !explored.has(n)).forEach(n => {
                explored.add(n);
                distances[n] = distances[t] == undefined ? 1 : distances[t] + 1;
                q.enqueue(n);
            });
        }
        return distances[n2];
    }
    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;
    }
    kruskalsMST() {
        // MST रखने वाला ग्राफ इनिशियलाइज़ करें
        const MST = new Graph();
        this.nodes.forEach(node => MST.addNode(node));
        if (this.nodes.length === 0) {
            return MST;
        }
        // प्रायोरिटी क्यू बनाएं
        let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
        // सभी एजेज को क्यू में जोड़ें:
        for (let node in this.edges) {
            this.edges[node].forEach(edge => {
                edgeQueue.enqueue([node, edge.node], edge.weight);
            });
        }
        let uf = new UnionFind(this.nodes);
        // तब तक लूप करें जब तक हम सभी नोड्स एक्सप्लोर न कर लें या क्यू खाली न हो जाए
        while (!edgeQueue.isEmpty()) {
            // डिस्ट्रक्चरिंग का उपयोग करके एज डेटा प्राप्त करें
            let nextEdge = edgeQueue.dequeue();
            let nodes = nextEdge.data;
            let weight = nextEdge.priority;
            if (!uf.connected(nodes[0], nodes[1])) {
                MST.addEdge(nodes[0], nodes[1], weight);
                uf.union(nodes[0], nodes[1]);
            }
        }
        return MST;
    }
    djikstraAlgorithm(startNode) {
        let distances = {};
        // पिछले नोड्स का रेफरेंस स्टोर करता है
        let prev = {};
        let pq = new PriorityQueue(this.nodes.length * this.nodes.length);
        // सभी नोड्स की दूरियों को स्टार्टनोड को छोड़कर इनफिनिटी पर सेट करें
        distances[startNode] = 0;
        pq.enqueue(startNode, 0);
        this.nodes.forEach(node => {
            if (node !== startNode) distances[node] = Infinity;
            prev[node] = null;
        });
        while (!pq.isEmpty()) {
            let minNode = pq.dequeue();
            let currNode = minNode.data;
            let weight = minNode.priority;
            this.edges[currNode].forEach(neighbor => {
                let alt = distances[currNode] + neighbor.weight;
                if (alt < distances[neighbor.node]) {
                    distances[neighbor.node] = alt;
                    prev[neighbor.node] = currNode;
                    pq.enqueue(neighbor.node, distances[neighbor.node]);
                }
            });
        }
        return distances;
    }
    floydWarshallAlgorithm() {
        let dist = {};
        for (let i = 0; i < this.nodes.length; i++) {
            dist[this.nodes[i]] = {};
            // मौजूदा एज के लिए डिस्ट को वजन के समान असाइन करें
            this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
            this.nodes.forEach(n => {
                // अन्य सभी नोड्स के लिए इसे इनफिनिटी असाइन करें
                if (dist[this.nodes[i]][n] == undefined)
                    dist[this.nodes[i]][n] = Infinity;
                // सेल्फ एज के लिए डिस्ट को 0 असाइन करें
                if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
            });
        }
        this.nodes.forEach(i => {
            this.nodes.forEach(j => {
                this.nodes.forEach(k => {
                    // जांचें कि i से k फिर k से j जाना बेहतर है
                    // सीधे i से j जाने से। अगर हां तो अपडेट करें
                    // i से j वैल्यू को नई वैल्यू से
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                });
            });
        });
        return dist;
    }
}
class UnionFind {
    constructor(elements) {
        // डिस्कनेक्टेड कंपोनेंट्स की संख्या
        this.count = elements.length;
        // कनेक्टेड कंपोनेंट्स को ट्रैक करें
        this.parent = {};
        // डेटा संरचना को इनिशियलाइज़ करें ताकि सभी एलिमेंट्स के पैरेंट वे स्वयं हों
        elements.forEach(e => (this.parent[e] = e));
    }
    union(a, b) {
        let rootA = this.find(a);
        let rootB = this.find(b);
        // रूट समान हैं तो ये पहले से कनेक्टेड हैं।
        if (rootA === rootB) return;
        // हमेशा छोटे रूट वाले एलिमेंट को पैरेंट बनाएं।
        if (rootA < rootB) {
            if (this.parent[b] != b) this.union(this.parent[b], a);
            this.parent[b] = this.parent[a];
        } else {
            if (this.parent[a] != a) this.union(this.parent[a], b);
            this.parent[a] = this.parent[b];
        }
    }
    // नोड का अंतिम पैरेंट लौटाता है
    find(a) {
        while (this.parent[a] !== a) {
            a = this.parent[a];
        }
        return a;
    }
    // 2 नोड्स की कनेक्टिविटी जांचता है
    connected(a, b) {
        return this.find(a) === this.find(b);
    }
}