क्रुस्कल का एल्गोरिदम एक लालची एल्गोरिदम है जो इस प्रकार काम करता है:
1. यह ग्राफ में सभी एजेज का एक सेट बनाता है।
2. जब तक उपरोक्त सेट खाली नहीं है और सभी वर्टेक्स कवर नहीं हो जाते,
- यह इस सेट से न्यूनतम वजन वाली एज को हटाता है
- यह जांचता है कि यह एज साइकिल बना रही है या सिर्फ 2 ट्री को जोड़ रही है। अगर यह साइकिल बनाती है, तो हम इस एज को छोड़ देते हैं, अन्यथा हम इसे अपने ट्री में जोड़ते हैं।
3. जब उपरोक्त प्रोसेसिंग पूरी हो जाती है, तो हमारे पास न्यूनतम स्पैनिंग ट्री होता है।
इस एल्गोरिदम को लागू करने के लिए, हमें 2 और डेटा संरचनाओं की आवश्यकता होती है।
पहले, हमें एक प्रायोरिटी क्यू की आवश्यकता होती है जिसका उपयोग हम एजेज को सॉर्टेड ऑर्डर में रखने और प्रत्येक इटरेशन पर अपनी आवश्यक एज प्राप्त करने के लिए कर सकते हैं।
अगला, हमें एक डिस्जॉइंट सेट डेटा संरचना की आवश्यकता होती है। एक डिस्जॉइंट-सेट डेटा संरचना (जिसे यूनियन-फाइंड डेटा संरचना या मर्ज-फाइंड सेट भी कहा जाता है) एक डेटा संरचना है जो एलिमेंट्स के एक सेट को ट्रैक करती है जो डिस्जॉइंट (नॉन-ओवरलैपिंग) सबसेट्स में विभाजित होते हैं। जब भी हम ट्री में एक नया नोड जोड़ते हैं, हम जांचेंगे कि क्या वे पहले से कनेक्टेड हैं। अगर हां, तो हमारे पास साइकिल है। अगर नहीं, तो हम एज के दोनों वर्टेक्स का यूनियन करेंगे। यह उन्हें उसी सबसेट में जोड़ देगा।
आइए यूनियनफाइंड या डिस्जॉइंटसेट डेटा संरचना के कार्यान्वयन को देखते हैं:
उदाहरण
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;
}
// 2 नोड्स की कनेक्टिविटी जांचता है
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
