কৃষ্কালের অ্যালগরিদম একটি লালচী (greedy) অ্যালগরিদম যা নিচের মত কাজ করে:
১. এটি গ্রাফের সব এজের একটি সেট তৈরি করে।
২. যতক্ষণ উপরের সেট খালি নয় এবং সব ভারটেক্স কভার হয়নি,
- এটি এই সেট থেকে মিনিমাম ওয়েটের এজটি রিমুভ করে
- এটি চেক করে এই এজটি সাইকেল ফর্ম করছে কিনা বা শুধু ২টি ট্রি কানেক্ট করছে। যদি সাইকেল ফর্ম করে, তবে এই এজটি ডিসকার্ড করা হয়, অন্যথায় আমরা এটিকে আমাদের ট্রিতে যোগ করি।
৩. উপরের প্রসেসিং কমপ্লিট হলে, আমাদের একটি মিনিমাম স্প্যানিং ট্রি থাকে।
এই অ্যালগরিদম বাস্তবায়ন করতে, আমাদের ২টি আর ডেটা স্ট্রাকচার দরকার।
প্রথমে, আমাদের একটি প্রায়োরিটি কিউ দরকার যা আমরা এজগুলোকে সর্টেড অর্ডারে রাখতে এবং প্রতিটি ইটারেশনে আমাদের রিকোয়ার্ড এজ পেতে ব্যবহার করব।
পরবর্তী, আমাদের একটি ডিসজয়েন্ট সেট ডেটা স্ট্রাকচার দরকার। একটি ডিসজয়েন্ট-সেট ডেটা স্ট্রাকচার (যাকে ইউনিয়ন-ফাইন্ড ডেটা স্ট্রাকচার বা মার্জ-ফাইন্ড সেটও বলা হয়) হলো একটি ডেটা স্ট্রাকচার যা এলিমেন্টের একটি সেটকে ট্র্যাক রাখে যেটি কিছু ডিসজয়েন্ট (নন-ওভারল্যাপিং) সাবসেটে পার্টিশন করা থাকে। যতক্ষণ আমরা একটি ট্রিতে নতুন নোড যোগ করি, আমরা চেক করব তারা ইতিমধ্যে কানেক্টেড কিনা। যদি হ্যাঁ হয়, তবে আমাদের একটি সাইকেল আছে। যদি না হয়, তবে আমরা এজের দুটি ভারটেক্সের ইউনিয়ন করব। এতে সেগুলো একই সাবসেটে যোগ হবে।
আসুন UnionFind বা DisjointSet ডেটা স্ট্রাকচার এর বাস্তবায়ন দেখি:
উদাহরণ
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);
}
}
আপনি নিচের কোড দিয়ে এটি পরীক্ষা করতে পারেন:
উদাহরণ
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() {
// MST থাকবে এমন গ্রাফ ইনিশিয়ালাইজ করুন
const MST = new Graph();
this.nodes.forEach(node => MST.addNode(node));
if (this.nodes.length === 0) {
return MST;
}
// একটি প্রায়োরিটি কিউ তৈরি করুন
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;
}
আপনি নিচের কোড দিয়ে এটি পরীক্ষা করতে পারেন:
উদাহরণ
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
