এই কোডে কমেন্ট আউট করা ফাংশনগুলো। আপনি সেগুলোও ব্যবহার করতে পারেন। আমরা Queue, Stack, এবং PriorityQueue ক্লাসগুলো আলাদা মডিউলে রেখেছি যেগুলো import statements বা require কল দিয়ে ইম্পোর্ট করা যায়। এখানে Graph ক্লাসের পূর্ণ বাস্তবায়ন দেওয়া হলো:
উদাহরণ
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);
// ১. edges অবজেক্টে, আমরা সেসে নোডগুলো খুঁজব যেগুলো এই নোডের সাথে সরাসরি কানেক্টেড।
// ২. আমরা যে নোডগুলোর ইতিমধ্যে এক্সপ্লোর করা হয়েছে সেগুলো ফিল্টার আউট করব।
// ৩. তারপর প্রতিটি আনএক্সপ্লোরড নোডকে এক্সপ্লোরড মার্ক করব এবং স্ট্যাকে পুশ করব।
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;
// সেলফ এজের জন্য ডিস্ট্যান্স ০ অ্যাসাইন করুন
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;
}
// ২টি নোডের কানেক্টিভিটি চেক করে
connected(a, b) {
return this.find(a) === this.find(b);
}
}
