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

<घंटा/>

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

औपचारिक रूप से, ग्राफ़ सेटों का एक युग्म होता है (V, E) , जहां V शीर्षों का समुच्चय है और E किनारों का समुच्चय है, जो शीर्षों के युग्मों को जोड़ता है। निम्नलिखित ग्राफ़ पर एक नज़र डालें -

ऊपर दिए गए ग्राफ़ में,

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

शब्दावली

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

वर्टेक्स - ग्राफ के प्रत्येक नोड को एक शीर्ष के रूप में दर्शाया गया है। निम्नलिखित उदाहरण में, लेबल वाला वृत्त शीर्षों का प्रतिनिधित्व करता है। अत:A से G शीर्ष हैं। हम एक सरणी का उपयोग करके उनका प्रतिनिधित्व कर सकते हैं जैसा कि निम्न छवि में दिखाया गया है। यहां ए को इंडेक्स 0 से पहचाना जा सकता है। बी को इंडेक्स 1 और इसी तरह से पहचाना जा सकता है।
किनारे - किनारा दो शीर्षों के बीच पथ या दो शीर्षों के बीच की रेखा का प्रतिनिधित्व करता है। निम्नलिखित उदाहरण में, ए से बी, बी से सी, और इसी तरह की रेखाएं किनारों का प्रतिनिधित्व करती हैं। हम निम्न छवि में दिखाए गए अनुसार एक सरणी का प्रतिनिधित्व करने के लिए द्वि-आयामी सरणी का उपयोग कर सकते हैं। यहाँ AB को पंक्ति 0 पर 1 के रूप में, कॉलम 1, BC को पंक्ति 1, कॉलम 2 पर 1 के रूप में और इसी तरह अन्य संयोजनों को 0 के रूप में दर्शाया जा सकता है।
आसन्नता - दो नोड या कोने आसन्न होते हैं यदि वे एक दूसरे से एक किनारे से जुड़े होते हैं। निम्नलिखित उदाहरण में, B, A के निकट है, C, B के निकट है, इत्यादि।
पथ -पथ दो शीर्षों के बीच किनारों के अनुक्रम का प्रतिनिधित्व करता है। निम्नलिखित उदाहरण में, ABCD A से D तक के पथ का प्रतिनिधित्व करता है।

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

उदाहरण

const Queue =आवश्यकता ("./Queue");const Stack =आवश्यकता ("./Stack");const प्रायोरिटीक्यू =आवश्यकता ("./PriorityQueue");वर्ग ग्राफ़ {कन्स्ट्रक्टर() { this.edges ={}; यह नोड्स =[]; } एडनोड (नोड) {this.nodes.push (नोड); यह किनारों [नोड] =[]; } addEdge (नोड 1, नोड 2, वजन =1) { यह किनारों [नोड 1]। पुश ({नोड:नोड 2, वजन:वजन}); this.edges[node2].push({node:node1, weight:weight}); } addDirectedEdge (नोड 1, नोड 2, वजन =1) { यह किनारों [नोड 1]। पुश ({नोड:नोड 2, वजन:वजन}); } // addEdge (नोड1, नोड 2) {// this.edges[node1].push(node2); // यह। किनारों [नोड 2]। पुश (नोड 1); // } // addDirectedEdge(node1, node2) {// this.edges[node1].push(node2); // } प्रदर्शन () { ग्राफ ="" दें; this.nodes.forEach(नोड => {ग्राफ +=नोड + "->" + this.edges[node].map(n => n.node).join(", ") + "\n"; } ); कंसोल.लॉग (ग्राफ); } बीएफएस (नोड) {चलो क्यू =नई कतार (यह। नोड्स। लंबाई); चलो पता लगाया =नया सेट (); क्यू.एनक्यू (नोड); एक्सप्लोर.एड (नोड); जबकि (!q.isEmpty ()) { टी =q.dequeue (); कंसोल.लॉग (टी); this.edges[t].filter(n => !explored.has(n)).forEach(n => {explored.add(n); q.enqueue(n); }); } } DFS (नोड) {// एक स्टैक बनाएं और उसमें अपना प्रारंभिक नोड जोड़ें s =new Stack(this.nodes.length); चलो पता लगाया =नया सेट (); एस.पुश (नोड); // पहले नोड को एक्सप्लोर किए गए के रूप में चिह्नित करें। जोड़ें (नोड); // हम तब तक जारी रखेंगे जब तक हमारा स्टैक खाली नहीं हो जाता (!s.isEmpty ()) {let t =s.pop (); // स्टैक कंसोल से बाहर आने वाले प्रत्येक तत्व को लॉग करें। लॉग (टी); // 1. किनारों की वस्तु में, हम उन नोड्स की खोज करते हैं जिनसे यह नोड सीधे जुड़ा हुआ है। // 2. हम उन नोड्स को फ़िल्टर करते हैं जिन्हें पहले ही खोजा जा चुका है। // 3. फिर हम प्रत्येक बेरोज़गार नोड को खोजे गए के रूप में चिह्नित करते हैं और इसे स्टैक पर धकेलते हैं। this.edges[t].filter(n => !explored.has(n)).forEach(n => {explored.add(n); s.push(n); }); } } टोपोलॉजिकलसॉर्ट हेल्पर (नोड, एक्सप्लोर, एस) { एक्सप्लोर.एड (नोड); this.edges[node].forEach(n => { if (!explored.has(n)) {this.topologicalSortHelper(n, explored, s); }}); एस.पुश (नोड); } टोपोलॉजिकलसॉर्ट () {// एक स्टैक बनाएं और उसमें हमारा प्रारंभिक नोड जोड़ें s =new Stack(this.nodes.length); चलो पता लगाया =नया सेट (); this.nodes.forEach(नोड => { अगर (!explored.has(node)) {this.topologicalSortHelper(node, explored, s); }}); जबकि (!s.isEmpty ()) { कंसोल.लॉग (s.pop ()); } } BFSShortestPath(n1, n2) { चलो q =नई कतार (this.nodes.length); चलो पता लगाया =नया सेट (); चलो दूरियाँ ={n1:0}; क्यू.एनक्यू (एन1); एक्सप्लोर.एड (n1); जबकि (!q.isEmpty ()) { टी =q.dequeue (); this.edges[t].filter(n => !explored.has(n)).forEach(n => { explore.add(n); दूरी [एन] =दूरी [टी] ==अपरिभाषित? 1:दूरी [टी] + 1; क्यू.एनक्यू (एन); }); } वापसी दूरी [n2]; } primsMST() {// ग्राफ़ को प्रारंभ करें जिसमें MST const MST =नया ग्राफ़ (); अगर (this.nodes.length ===0) { MST लौटाएं; } // आरंभिक नोड के रूप में पहले नोड का चयन करें लेट्स s =this.nodes [0]; // एक प्रायोरिटी कतार बनाएं और एक्सप्लोर किया गया सेट लेट एजक्यू =नई प्रायोरिटी क्यू (यह। नोड्स। लंबाई * यह। नोड्स। लंबाई); चलो पता लगाया =नया सेट (); एक्सप्लोर.एड (एस); MST.addNode(s); // इस प्रारंभिक नोड से सभी किनारों को प्राथमिकता के रूप में भार लेते हुए PQ में जोड़ें। // सबसे छोटा किनारा लें और उसे नए ग्राफ में जोड़ें currentMinEdge =edgeQueue.dequeue (); जबकि (! edgeQueue.isEmpty ()) {// किनारों को हटाना जारी रखें जब तक कि हमें एक अस्पष्टीकृत नोड के साथ एक किनारा न मिल जाए, जबकि (!edgeQueue.isEmpty() &&explored.has(currentMinEdge.data[1])) {currentMinEdge =edgeQueue. dequeue (); } चलो nextNode =currentMinEdge.data[1]; // फिर से जांचें क्योंकि अगर (!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); }); // इस नोड को एक्सप्लोर किए गए के रूप में चिह्नित करें। जोड़ें (अगला नोड); एस =अगला नोड; } } एमएसटी वापसी; } kruskalsMST () {// ग्राफ़ को प्रारंभ करें जिसमें MST const MST =नया ग्राफ़ (); this.nodes.forEach (नोड => MST.addNode (नोड)); अगर (this.nodes.length ===0) { MST लौटाएं; ] // कतार में सभी किनारों को जोड़ें:के लिए (इस.किनारों में नोड दें) {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]); } } एमएसटी वापसी; } djikstraAlgorithm(startNode) { चलो दूरियां ={}; // पिछले नोड्स के संदर्भ को संग्रहीत करता है prev ={}; चलो pq =नई प्राथमिकता कतार (यह। नोड्स। लंबाई * यह। नोड्स। लंबाई); // startNode दूरी [स्टार्टनोड] =0 को छोड़कर सभी नोड्स के लिए दूरी को अनंत होने के लिए सेट करें; pq.enqueue(startNode, 0); this.nodes.forEach (नोड => {अगर (नोड! ==startNode) दूरियां [नोड] =अनंत; पिछला [नोड] =अशक्त; }); जबकि (! pq.isEmpty ()) { minNode =pq.dequeue (); चलो currNode =minNode.data; चलो वजन =minNode.priority; this.edges[currNode].forEach (पड़ोसी => { चलो alt =दूरी [currNode] + पड़ोसी। वजन; अगर (alt <दूरी [पड़ोसी। नोड]) {दूरी [पड़ोसी। नोड] =alt; पिछला [पड़ोसी। नोड] =currNode; pq.enqueue (पड़ोसी.नोड, दूरी [पड़ोसी.नोड]); }}); } वापसी दूरी; } floydWarshallएल्गोरिदम () { लेट डिस्ट ={}; के लिए (चलो मैं =0; मैं  (dist[this.nodes[i]][e.node] =e.weight) ); this.nodes.forEach(n => {// अन्य सभी नोड्स के लिए इसे अनंत को असाइन करें यदि (dist[this.nodes[i]][n] ==undefined) dist[this.nodes[i]][n] =इन्फिनिटी; // सेल्फ एज के लिए डिस्ट को 0 पर असाइन करें यदि (यह। नोड्स [i] ===n) डिस्ट [यह। नोड्स [i]] [n] =0;});} this.nodes.forEach (i => {this.nodes.forEach(j => {this.nodes.forEach(k => {// जांचें कि क्या i से k तक जाना है तो k से j तक जाना बेहतर है // सीधे i से j तक जाने से) यदि हाँ तो नए मान के लिए // i से j मान को अपडेट करें यदि (जिला [i] [के] + जिला [के] [जे] <जिला [i] [जे]) जिला [i] [जे] =जिला [i][k] + dist[k][j]; }); });}); वापसी जिला;}}कक्षा UnionFind {कन्स्ट्रक्टर (तत्व) {// डिस्कनेक्ट किए गए घटकों की संख्या यह। गिनती =तत्व। लंबाई; // जुड़े हुए घटकों का ट्रैक रखें this.parent ={}; // डेटा संरचना को प्रारंभ करें जैसे कि सभी तत्व स्वयं माता-पिता तत्वों के रूप में हों। प्रत्येक के लिए (ई => (यह। माता-पिता [ई] =ई)); } संघ (ए, बी) { रूट ए =यह। ढूंढें (ए); चलो rootB =this.find(b); // रूट समान हैं इसलिए ये पहले से ही जुड़े हुए हैं। अगर (रूटए ===रूटबी) वापसी; // हमेशा छोटे रूट वाले तत्व को पैरेंट बनाएं। अगर (रूट ए <रूटबी) { अगर (यह माता-पिता [बी]! =बी) यह संघ (यह माता-पिता [बी], ए); यह। माता-पिता [बी] =यह। माता-पिता [ए]; } और { अगर (यह। माता-पिता [ए]! =ए) यह संघ (यह माता-पिता [ए], बी); यह। माता-पिता [ए] =यह। माता-पिता [बी]; } } // एक नोड के अंतिम पैरेंट को ढूंढता है (ए) { जबकि (यह। माता-पिता [ए]! ==ए) {ए =यह। माता-पिता [ए]; } रिटर्न ए;}// कनेक्टेड 2 नोड्स की कनेक्टिविटी की जांच करता है (ए, बी) { इसे वापस करें। ढूंढें (ए) ===यह। ढूंढें (बी); }}