প্রিমস অ্যালগরিদম (Prim's Algorithm) হলো একটি লোভী (greedy) পদ্ধতি যা ওজনযুক্ত অনির্দেশিত গ্রাফ (weighted undirected graph)-এর মিনিমাম স্প্যানিং ট্রি (MST) বের করতে ব্যবহৃত হয়।
পরিবhasa
- ওজনযুক্ত গ্রাফ: সব এজে ওয়েট (weight) থাকে
- অনির্দেশিত গ্রাফ: এজগুলো দ্বিমুখী (bidirectional)
- MST: সব ভের্টেক্স ও এজ থাকবে কিন্তু সাইকেল (cycle) থাকবে না, মোট ওয়েট ন্যূনতম হবে
সাদা বাস্তবায়ন (একটি অ্যারে ব্যবহার করে)
সাধারণত প্রিমস দুইটি অ্যারে ব্যবহার করে, কিন্তু এখানে শুধো একটি inMST বুলিয়ান ভেক্টর ব্যবহার করা হয়েছে।
C++ প্রোগ্রাম উদাহরণ
#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] && !inMST[v]) return false;
if (inMST[u] && inMST[v]) 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 && 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;
}
আউটপুট
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
