Prim's algorithm एक लालची एल्गोरिथम है जो भारित अप्रत्यक्ष ग्राफ के लिए न्यूनतम फैले हुए पेड़ को ढूंढता है। यह किनारों का एक सबसेट ढूंढता है जो एक पेड़ बनाता है जिसमें प्रत्येक शीर्ष शामिल होता है, जहां पेड़ के सभी किनारों का कुल वजन कम से कम होता है।
एल्गोरिथम इस पेड़ को एक बार में एक शीर्ष बनाकर, एक मनमाना शुरुआती शीर्ष से, प्रत्येक चरण में पेड़ से दूसरे शीर्ष पर सबसे सस्ता संभव कनेक्शन जोड़कर संचालित होता है।
प्राइम का एल्गोरिदम कैसे काम करता है?
आइए एक उदाहरण देखें कि प्राइम का एल्गोरिदम कैसे काम करता है -
1. रूट नोड के रूप में कोई भी मनमाना नोड चुनें:इस मामले में, हम प्राइम के फैले हुए पेड़ के रूट नोड के रूप में एस नोड को चुनते हैं। यह नोड मनमाने ढंग से चुना जाता है, इसलिए कोई भी नोड रूट नोड हो सकता है। किसी को आश्चर्य हो सकता है कि कोई वीडियो रूट नोड क्यों हो सकता है। तो जवाब है, फैले हुए पेड़ में एक ग्राफ के सभी नोड्स शामिल हैं और क्योंकि यह जुड़ा हुआ है तो कम से कम एक किनारा होना चाहिए, जो इसे बाकी पेड़ से जोड़ देगा।
2. आउटगोइंग किनारों की जांच करें और कम लागत वाले एक का चयन करें:रूट नोड एस चुनने के बाद, हम देखते हैं कि एस, ए, और एस, सी क्रमशः 7 और 8 वजन वाले दो किनारे हैं। हम किनारे S, A को चुनते हैं क्योंकि यह दूसरे से छोटा है।
अब, पेड़ S-7-A को एक नोड के रूप में माना जाता है और हम इससे बाहर जाने वाले सभी किनारों की जांच करते हैं। हम उसे चुनते हैं जिसकी लागत सबसे कम है और इसे पेड़ में शामिल करते हैं।
इस चरण के बाद, S-7-A-3-C वृक्ष बनता है। अब हम इसे फिर से एक नोड के रूप में मानेंगे और फिर से सभी किनारों की जांच करेंगे। हालांकि, हम केवल कम से कम लागत वाली बढ़त का चयन करेंगे। इस मामले में, सी-3-डी नया किनारा है, जो अन्य किनारों की लागत 8, 6, 4, आदि से कम है।
नोड जोड़ने के बाद D फैले हुए पेड़ के लिए, अब हमारे पास समान लागत वाले दो किनारे हैं, यानी डी-2-टी और डी-2-बी। इस प्रकार, हम इनमें से किसी एक को जोड़ सकते हैं। लेकिन अगला कदम फिर से बढ़त 2 को कम से कम लागत के रूप में देगा। इसलिए, हम एक फैले हुए पेड़ को दिखा रहे हैं जिसमें दोनों किनारों को शामिल किया गया है।
अब देखते हैं कि हम इसे अपने कोड में कैसे लागू कर सकते हैं -
उदाहरण
primsMST() {
// Initialize graph that'll contain the MST
const MST = new Graph();
if (this.nodes.length === 0) {
return MST;
}
// Select first node as starting node
let s = this.nodes[0];
// Create a Priority Queue and explored set
let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
let explored = new Set();
explored.add(s);
MST.addNode(s);
// Add all edges from this starting node to the PQ taking weights as priority
this.edges[s].forEach(edge => {
edgeQueue.enqueue([s, edge.node], edge.weight);
});
// Take the smallest edge and add that to the new graph
let currentMinEdge = edgeQueue.dequeue();
while (!edgeQueue.isEmpty()) {
// COntinue removing edges till we get an edge with an unexplored node
while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
currentMinEdge = edgeQueue.dequeue();
}
let nextNode = currentMinEdge.data[1];
// Check again as queue might get empty without giving back unexplored element
if (!explored.has(nextNode)) {
MST.addNode(nextNode);
MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);
// Again add all edges to the PQ
this.edges[nextNode].forEach(edge => {
edgeQueue.enqueue([nextNode, edge.node], edge.weight);
});
// Mark this node as explored explored.add(nextNode);
s = nextNode;
}
}
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.primsMST().display(); आउटपुट
यह आउटपुट देगा -
A->B, D B->A, G D->A, C, E C->D E->D, F G->B F->E
ध्यान दें कि हमारा प्रारंभिक ग्राफ था -
उदाहरण
/** * A * / | \ * C | B * \ | | * D G * | / * E * | * F */
आउटपुट
हमारा वर्तमान ग्राफ इस तरह दिखता है -
/** * A * |\ * C | B * \ | | * D G * | * E * | * F * */
हमने सबसे महंगे किनारों को हटा दिया है और अब एक फैला हुआ पेड़ है।