প্রিমের অ্যালগরিদম একটি লোভী পদ্ধতি যা প্রদত্ত ওজনযুক্ত অনির্দেশিত গ্রাফের জন্য ন্যূনতম বিস্তৃত গাছ খুঁজে বের করতে ব্যবহৃত হয়৷
ভারিত গ্রাফ একটি গ্রাফ যার ওজন মান সহ সমস্ত প্রান্ত রয়েছে৷
৷অনির্দেশিত গ্রাফ একটি বিশেষ ধরনের গ্রাফ যার সব প্রান্ত দ্বিমুখী।
সর্বনিম্ন বিস্তৃত গাছ একটি উপসেট যাতে সমস্ত প্রান্ত এবং শীর্ষবিন্দু রয়েছে কিন্তু কোনো চক্র নেই এবং সর্বনিম্ন সম্ভাব্য মোট প্রান্তের ওজন রয়েছে৷
এই নিবন্ধে, আমরা ন্যূনতম স্প্যানিং ট্রি খুঁজে বের করার জন্য প্রাইমের অ্যালগরিদম সম্পর্কে শিখব। সাধারণত, অ্যালগরিদম দুটি অ্যারে ব্যবহার করে কিন্তু এই সমাধানে, আমরা শুধুমাত্র একটি ব্যবহার করব৷
প্রাইমের অ্যালগরিদমের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define V 5
bool createsMST(int u, int v, vector<bool> inMST){
if (u == v)
return false;
if (inMST[u] == false && inMST[v] == false)
return false;
else if (inMST[u] == true && inMST[v] == true)
return false;
return true;
}
void printMinSpanningTree(int cost[][V]){
vector<bool> inMST(V, false);
inMST[0] = true;
int edgeNo = 0, MSTcost = 0;
while (edgeNo < V - 1) {
int min = INT_MAX, a = -1, b = -1;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (cost[i][j] < min) {
if (createsMST(i, j, inMST)) {
min = cost[i][j];
a = i;
b = j;
}
}
}
}
if (a != -1 && b != -1) {
cout<<"Edge "<<edgeNo++<<" : ("<<a<<" , "<<b<<" ) : cost = "<<min<<endl;
MSTcost += min;
inMST[b] = inMST[a] = true;
}
}
cout<<"Cost of Minimum spanning tree ="<<MSTcost;
}
int main() {
int cost[][V] = {
{ INT_MAX, 12, INT_MAX, 25, INT_MAX },
{ 12, INT_MAX, 11, 8, 12 },
{ INT_MAX, 11, INT_MAX, INT_MAX, 17 },
{ 25, 8, INT_MAX, INT_MAX, 15 },
{ INT_MAX, 12, 17, 15, INT_MAX },
};
cout<<"The Minimum spanning tree for the given tree is :\n";
printMinSpanningTree(cost);
return 0;
} আউটপুট
The Minimum spanning tree for the given tree is : Edge 0 : (0 , 1 ) : cost = 12 Edge 1 : (1 , 3 ) : cost = 8 Edge 2 : (1 , 2 ) : cost = 11 Edge 3 : (1 , 4 ) : cost = 12 Cost of Minimum spanning tree =43
