জাভাস্ক্রিপ্টে ক্রুস্কালের অ্যালগরিদম

ক্রুসকালের অ্যালগরিদম হল একটি লোভী অ্যালগরিদম যা নিম্নরূপ কাজ করে −

1. এটি গ্রাফের সমস্ত প্রান্তের একটি সেট তৈরি করে৷

2. যদিও উপরের সেটটি খালি নয় এবং সমস্ত শীর্ষবিন্দু কভার করা হয় না,

• এটি এই সেট থেকে সর্বনিম্ন ওজন প্রান্ত সরিয়ে দেয়
• এটি পরীক্ষা করে যে এই প্রান্তটি একটি চক্র তৈরি করছে নাকি শুধু 2টি গাছকে সংযুক্ত করছে। যদি এটি একটি চক্র গঠন করে, আমরা এই প্রান্তটি বাতিল করে দিই, অন্যথায় আমরা এটিকে আমাদের গাছে যুক্ত করি৷

3. উপরের প্রক্রিয়াকরণ সম্পূর্ণ হলে, আমাদের কাছে একটি ন্যূনতম বিস্তৃত গাছ আছে৷

এই অ্যালগরিদম বাস্তবায়ন করার জন্য, আমাদের আরও 2টি ডেটা স্ট্রাকচার প্রয়োজন৷

প্রথমত, আমাদের একটি অগ্রাধিকার সারি প্রয়োজন যা আমরা প্রান্তগুলিকে সাজানো ক্রমে রাখতে এবং প্রতিটি পুনরাবৃত্তিতে আমাদের প্রয়োজনীয় প্রান্ত পেতে ব্যবহার করতে পারি৷

এর পরে, আমাদের একটি ডিসজয়েন্ট সেট ডেটা স্ট্রাকচার দরকার। একটি ডিসজয়েন্ট-সেট ডেটা স্ট্রাকচার (যাকে ইউনিয়ন-ফাইন্ড ডেটা স্ট্রাকচার বা মার্জ-ফাইন্ড সেটও বলা হয়) হল একটি ডেটা স্ট্রাকচার যা অনেকগুলি ডিসজয়েন্ট (নন-ওভারল্যাপিং) উপসেটে বিভক্ত উপাদানগুলির একটি সেটকে ট্র্যাক করে। যখনই আমরা একটি গাছে একটি নতুন নোড যোগ করি, আমরা পরীক্ষা করব যে তারা ইতিমধ্যে সংযুক্ত কিনা। যদি হ্যাঁ, তাহলে আমাদের একটি চক্র আছে। যদি না হয়, আমরা প্রান্তের উভয় শীর্ষবিন্দুর একটি মিলন করব। এটি তাদের একই উপসেটে যুক্ত করবে৷

আসুন আমরা UnionFind বা DisjointSet ডেটা স্ট্রাকচার &minsu;

উদাহরণ

class UnionFind {
   constructor(elements) {
      // Number of disconnected components
      this.count = elements.length;

      // Keep Track of connected components
      this.parent = {};

      // Initialize the data structure such that all
      // elements have themselves as parents
      elements.forEach(e => (this.parent[e] = e));
   }

   union(a, b) {
      let rootA = this.find(a);
      let rootB = this.find(b);

      // Roots are same so these are already connected.
      if (rootA === rootB) return;

      // Always make the element with smaller root the parent.
      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];
      }
   }

   // Returns final parent of a node
   find(a) {
      while (this.parent[a] !== a) {
         a = this.parent[a];
      }
      return a;
   }

   // Checks connectivity of the 2 nodes
   connected(a, b) {
      return this.find(a) === this.find(b);
   }
}

আপনি −

উদাহরণ

let uf = new UnionFind(["A", "B", "C", "D", "E"]);
uf.union("A", "B"); uf.union("A", "C");
uf.union("C", "D");

console.log(uf.connected("B", "E"));
console.log(uf.connected("B", "D"));

আউটপুট

এটি −

false
true

এখন আসুন এই ডাটা স্ট্রাকচার ব্যবহার করে ক্রুসকালের অ্যালগরিদমের বাস্তবায়ন দেখি -

উদাহরণ

kruskalsMST() {
   // Initialize graph that'll contain the MST
   const MST = new Graph();
   this.nodes.forEach(node => MST.addNode(node));
   if (this.nodes.length === 0) {
      return MST;
   }

   // Create a Priority Queue
   edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);

   // Add all edges to the Queue:
   for (let node in this.edges) {
      this.edges[node].forEach(edge => {
         edgeQueue.enqueue([node, edge.node], edge.weight);
      });
   }

   let uf = new UnionFind(this.nodes);

   // Loop until either we explore all nodes or queue is empty
   while (!edgeQueue.isEmpty()) {
      // Get the edge data using destructuring
      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;
}

আপনি −

উদাহরণ

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");

g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("C", "D", 3);
g.addEdge("D", "E", 8);
g.addEdge("E", "F", 10);
g.addEdge("B", "G", 9);
g.addEdge("E", "G", 50);

g.kruskalsMST().display();

আউটপুট

এটি −

A->B, D
B->A, G
C->D
D->C, A, E
E->D, F
F->E
G->B