প্রিমের অ্যালগরিদম একটি লালচী (greedy) অ্যালগরিদম যা একটি ওয়েটেড আনডাইরেক্টেড গ্রাফের জন্য একটি মিনিমাম স্প্যানিং ট্রি (MST) খুঁজে বের করে। এটি এজের একটি সাবসেট খুঁজে বের করে যা একটি ট্রি ফর্ম করে যেটি সব ভারটেক্স ইনক্লুড করে, যেখানে ট্রির সব এজের টোটাল ওয়েট মিনিমাইজড থাকে।
এই অ্যালগরিদম একসাথে এক ভেরটেক্স করে এই ট্রি বিল্ড করে, একটি আর্কিট্রেরি স্টার্টিং ভারটেক্স থেকে, প্রতিটি স্টেপে ট্রি থেকে অন্য একটি ভারটেক্সের সাথে সবচেয়ে সস্তা কানেকশন যোগ করে।
প্রিমের অ্যালগরিদম কীভাবে কাজ করে?
আসুন প্রিমের অ্যালগরিদম কীভাবে কাজ করে তার একটি ইলাস্ট্রেশন দেখি:
১. যেকোনো আর্বিট্রারি নোডকে রুট নোড হিসেবে বেছে নিন: এই কেসে, আমরা S নোডকে প্রিমের স্প্যানিং ট্রির রুট নোড হিসেবে বেছে নেই। এই নোডটি আর্বিট্রেরিলি বেছে নেওয়া হয়েছে, তাই যেকোনো নোড রুট নোড হতে পারে। কেউ চিন্তা করতে পারে কেন যেকোনো ভেরটেক্স রুট নোড হতে পারে। তাই উত্তর হলো, স্প্যানিং ট্রিতে একটি গ্রাফের সব নোড ইনক্লুড থাকে এবং কারণ এটি কানেক্টেড থাকলে কমপক্ষে একটি এজ অবশ্যই থাকবে, যা এটিকে বাকি ট্রির সাথে জয়েন করবে।
২. আউটগোইং এজগুলো চেক করুন এবং কম খরচের একটা সিলেক্ট করুন: রুট নোড S বেছে নেওয়ার পর, আমরা দেখি S, A এবং S, C দুটি এজ আছে যাদের ওয়েট ৭ এবং ৮। আমরা S, A এজটি বেছে নেই কারণ এটি অন্যটির চেয়ে কম।
এখন, S-7-A ট্রিকে একটি নোড হিসেবে বিবেচনা করা হয় এবং আমরা সেটি থেকে বের হওয়া সব এজ চেক করি। আমরা সেটি সিলেক্ট করি যেটির খরচ সবচেয়ে কম এবং ট্রিতে ইনক্লুড করি।
এই ধাপের পর, S-7-A-3-C ট্রি ফর্ম হয়েছে। এখন আমরা আবার এটিকে একটি নোড হিসেবে বিবেচনা করব এবং সব এজ আবার চেক করব। যাইহোক, আমরা শুধু কম খরচের এজটি বেছে নেব। এই কেসে, C-3-D হলো নতুন এজটি, যা অন্যান্য এজগুলোর খরচ ৮, ৬, ৪, ইত্যাদির চেয়ে কম।
নোড D স্প্যানিং ট্রিতে যোগ হওয়ার পর, এখন এর থেকে বের হওয়া দুটি এজ আছে যাদের একই খরচ, অর্থাৎ D-2-T এবং D-2-B। সুতরাং, আমরা যেকোনো একটি যোগ করতে পারি। কিন্তু পরবর্তী ধাপে আবার এজ ২ শর্টেস্ট কষ্ট দেবে। তাই, আমরা উভয় এজ ইনক্লুড করা একটি স্প্যানিং ট্রি দেখাচ্ছি।
এখন আসুন দেখি কীভাবে আমরা আমাদের কোডে একই জিনিসটি বাস্তবায়ন করতে পারি:
উদাহরণ
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;
}
আপনি নিচের কোড দিয়ে এটি পরীক্ষা করতে পারেন:
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 * */
আমরা সবচেয়ে ব্যয়বহুল এজগুলো রিমুভ করেছি এবং এখন একটি স্প্যানিং ট্রি আছে।
