প্রিমস ন্যূনতম স্প্যানিং ট্রি অ্যালগরিদম

একটি সংযুক্ত গ্রাফ G(V, E) দেওয়া আছে এবং প্রতিটি এজের ওজন বা খরচ জানা আছে। প্রিমস অ্যালগরিদম গ্রাফ G থেকে ন্যূনতম স্প্যানিং ট্রি বের করে।

এটি একটি বৃদ্ধিশীল ট্রি পদ্ধতি। এই অ্যালগরিদম ট্রি শুরু করার জন্য একটি সিড ভ্যালু (seed value) নেয়। সিড ভার্টেক্স থেকে শুরু করে পুরো ট্রি গঠন করা হয়।

সমস্যাটি দুটি সেট ব্যবহার করে সমাধান করা হয়। একটি সেট ইতিমধ্যে নির্বাচিত নোডগুলো ধারণ করে, আরেকটি সেট এখনো বিবেচনা করা হয়নি এমন নোডগুলো রাখে। সিড ভার্টেক্স থেকে প্রারম্ভ করে, ন্যূনতম এজ খরচের ভিত্তিতে সংলগ্ন ভার্টেক্সগুলো নেওয়া হয়, এইভাবে এক-এক করে নোড যুক্ত করে ট্রিটি বড় করা হয়।

এই সমস্যার টাইম কমপ্লেক্সিটি O(V²)। এখানে V হলো ভার্টেক্সের সংখ্যা।

ইনপুট এবং আউটপুট

ইনপুট: এডজেসেন্সি লিস্ট:  আউটপুট: (0)---(1|1) (0)---(2|3) (0)---(3|4) (1)---(0|1) (1)---(4|2) (2)---(0|3) (3)---(0|4) (4)---(1|2) (4)---(5|2) (5)---(4|2) (5)---(6|3) (6)---(5|3)

অ্যালগরিদম

prims(g: Graph, t: tree, start)

ইনপুট - গ্রাফ g, একটি খালি ট্রি এবং 'start' নামে সিড ভার্টেক্স

আউটপুট - এজ যোগ করার পর ট্রি

শুরু
  usedVert, unusedVert নামে দুটি সেট ডিফাইন করুন
  usedVert[0] := start এবং unusedVert[0] := φ
  start ছাড়া সব ভের্টেক্সের জন্য করুন
    usedVert[i] := φ
    unusedVert[i] := i  // সব ভের্টেক্স অনইউজড লিস্টে যোগ করুন
  শেষ
  যতক্ষণ usedVert-এ ভের্টেক্সের সংখ্যা ≠ V করুন  // V মোট নোড সংখ্যা
    min := ∞
    usedVert অ্যারেতে সব ভের্টেক্সের জন্য করুন
      গ্রাফের সব ভের্টেক্সের জন্য করুন
        যদি min > cost[i,j] এবং i ≠ j হয়, তবে
          min := cost[i,j]
          ed := i এবং j এর মধ্যে এজ, এবং ed-এর খরচ := min
      শেষ
    শেষ
    unusedVert[ed-এর ডেস্টিনেশন] := φ
    ট্রি t-তে ed এজটি যোগ করুন
    ed-এর সোর্স usedVert-এ যোগ করুন
  শেষ
শেষ

উদাহরণ

#include<iostream> #define V 7 #define INF 999 using namespace std; //গ্রাফের কস্ট ম্যাট্রিক্স int costMat[V][V] = { {0, 1, 3, 4, INF, 5, INF}, {1, 0, INF, 7, 2, INF, INF}, {3, INF, 0, INF, 8, INF, INF}, {4, 7, INF, 0, INF, INF, INF}, {INF, 2, 8, INF, 0, 2, 4}, {5, INF, INF, INF, 2, 0, 3}, {INF, INF, INF, INF, 4, 3, 0} }; typedef struct { int u, v, cost; }edge; class Tree { int n; edge edges[V-1]; //ট্রিতে vertex-1 টি এজ থাকে public: Tree() { n = 0; } void addEdge(edge e) { edges[n] = e; //ট্রিতে e এজটি যোগ করুন n++; } void printEdges() { //এজ, খরচ এবং মোট খরচ প্রিন্ট করুন int tCost = 0; for(int i = 0; i<n; i++) { cout << "Edge: " << char(edges[i].u+'A') << "--" << char(edges[i].v+'A'); cout << " And Cost: " << edges[i].cost << endl; tCost += edges[i].cost; } cout << "Total Cost: " << tCost << endl; } friend void prims(Tree &tre, int start); }; void prims(Tree &tr, int start) { int usedVert[V], unusedVert[V]; int i, j, min, p; edge ed; //ইনিশিয়ালাইজ usedVert[0] = start; p = 1; unusedVert[0] = -1; //-1 নির্দেশ করে প্লেসটি খালি for(i = 1; i<V; i++) { usedVert[i] = -1; //প্রথমটি ছাড়া সব প্লেস খালি unusedVert[i] = i; //ভার্টেক্স দিয়ে ফিল করুন } tr.n = 0; //এজ পাওয়া এবং ট্রিতে যোগ করা while(p != V) { //p usedVert অ্যারেতে ভের্টেক্সের সংখ্যা min = INF; for(i = 0; i<p; i++) { for(j = 0; j<V; j++) { if(unusedVert[j] != -1) { if(min > costMat[i][j] && costMat[i][j] != 0) { //ন্যূনতম খরচের এজ খুঁজুন //যাতে u বিবেচিত এবং v এখনো বিবেচিত নয় min = costMat[i][j]; ed.u = i; ed.v = j; ed.cost = min; } } } } unusedVert[ed.v] = -1; //v কে unusedVertex থেকে ডিলিট করুন tr.addEdge(ed); usedVert[p] = ed.u; p++; //u কে usedVertex-এ যোগ করুন } } main() { Tree tr; prims(tr, 0); //শুরু নোড 0 tr.printEdges(); }

আউটপুট

(0)---(1|1) (0)---(2|3) (0)---(3|4) (1)---(0|1) (1)---(4|2) (2)---(0|3) (3)---(0|4) (4)---(1|2) (4)---(5|2) (5)---(4|2) (5)---(6|3) (6)---(5|3)