जावास्क्रिप्ट में ग्राफ डेटा संरचना

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

औपचारिक रूप से, ग्राफ सेट का एक जोड़ा (V, E) है, जहां V वर्टेक्स का सेट है और E एज का सेट है, जो वर्टेक्स के जोड़े को जोड़ते हैं। निम्नलिखित ग्राफ को देखें:

उपरोक्त ग्राफ में,

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

टर्मिनोलॉजी

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

• वर्टेक्स - ग्राफ के प्रत्येक नोड को वर्टेक्स के रूप में दर्शाया जाता है। निम्नलिखित उदाहरण में, लेबल किया गया सर्कल वर्टेक्स को दर्शाता है। इस प्रकार, A से G वर्टेक्स हैं। हम उन्हें ऐरे का उपयोग करके दर्शा सकते हैं जैसा कि निम्नलिखित छवि में दिखाया गया है। यहां A को इंडेक्स 0 द्वारा पहचाना जा सकता है। B को इंडेक्स 1 का उपयोग करके पहचाना जा सकता है और इसी तरह।

• एज - एज दो वर्टेक्स के बीच एक पाथ या दो वर्टेक्स के बीच एक लाइन को दर्शाता है। निम्नलिखित उदाहरण में, A से B, B से C, और इसी तरह की लाइनें एज को दर्शाती हैं। हम दो-आयामी ऐरे का उपयोग करके एज को दर्शा सकते हैं जैसा कि निम्नलिखित छवि में दिखाया गया है। यहां AB को रो 0, कॉलम 1 पर 1 के रूप में दर्शाया जा सकता है, BC को रो 1, कॉलम 2 पर 1 के रूप में और इसी तरह, अन्य संयोजनों को 0 रखते हुए।

• एडजेसेंसी - दो नोड या वर्टेक्स एडजेसेंट हैं यदि वे एक एज के माध्यम से एक-दूसरे से जुड़े हुए हैं। निम्नलिखित उदाहरण में, B, A से एडजेसेंट है, C, B से एडजेसेंट है, और इसी तरह।

• पाथ - पाथ दो वर्टेक्स के बीच एज के अनुक्रम को दर्शाता है। निम्नलिखित उदाहरण में, ABCD, A से D तक का पाथ दर्शाता है।

यहां जावास्क्रिप्ट का उपयोग करके ग्राफ क्लास का पूरा कार्यान्वयन है।

उदाहरण

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);
    }
}