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

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

उदाहरण

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]][n] ==undefined) dist[this.nodes[i]][n] =इन्फिनिटी; // सेल्फ एज के लिए डिस्ट को 0 होने के लिए असाइन करें यदि (this.nodes[i] ===n) dist[this.nodes[i]][n] =0; }); } यह। सीधे i से j तक जा रहा है। यदि हाँ तो // i से j मान को नए मान में अपडेट करें यदि (dist[i][k] + dist[k][j]  (यह। माता-पिता [ई] =ई)); } संघ (ए, बी) { रूट ए =यह। ढूंढें (ए); चलो rootB =this.find(b); // रूट समान हैं इसलिए ये पहले से ही जुड़े हुए हैं। अगर (रूटए ===रूटबी) वापसी; // हमेशा छोटे रूट वाले तत्व को पैरेंट बनाएं। अगर (रूट ए <रूटबी) { अगर (यह माता-पिता [बी]! =बी) यह संघ (यह माता-पिता [बी], ए); यह। माता-पिता [बी] =यह। माता-पिता [ए]; } और { अगर (यह। माता-पिता [ए]! =ए) यह संघ (यह माता-पिता [ए], बी); यह। माता-पिता [ए] =यह। माता-पिता [बी]; } } // एक नोड के अंतिम पैरेंट को ढूंढता है (ए) { जबकि (यह। माता-पिता [ए]! ==ए) {ए =यह। माता-पिता [ए]; } वापसी एक; } // जुड़े हुए 2 नोड्स की कनेक्टिविटी की जांच करता है (ए, बी) { इसे लौटाएं। ढूंढें (ए) ===यह। ढूंढें (बी); }}