প্রিম'স (মিনিমাম স্প্যানিং ট্রি) MST অ্যালগরিদম

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

এটি গ্রোइং ট্রি এপ্রোচ্ছ। এই অ্যালগরিদমে ট্রি শুরু করার জন্য একটি সিড ভ্যালু দরকার। সিড ভার্টেক্স থেকে ট্রি পুরো আকার ধারণ করে।

সমস্যাটি দুটি সেট ব্যবহার করে সমাধান করা হবে। একটি সেট ইতিমধ্যে সিলেক্ট করা নোডগুলো রাখে, আরেকটি সেট آنকনসিডার্ড আইটেম রাখে। সিড ভার্টেক্স থেকে, এটি মিনিমাম এজ কস্টের ভিত্তিতে অ্যাডজেসেন্ট ভার্টেক্স নেয়, এইভাবে একে একে নোড নিয়ে ট্রি বড় করে।

• এই সমস্যার টাইম কমপ্লেক্সিটি 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'। আউটপুট: এজ যোগ করার পর ট্রি।

Begin
    define two sets as usedVert, unusedVert
    usedVert[0] := start and unusedVert[0] := φ
    for all vertices except start do
        usedVert[i] := φ
        unusedVert[i] := i //add all vertices in unused list
    done
    while number of vertices in usedVert ≠ V do //V is number of total nodes
        min := ∞
        for all vertices of usedVert array do
            for all vertices of the graph do
                if min > cost[i,j] AND i ≠ j then
                    min := cost[i,j]
                    ed := edge between i and j, and cost of ed := min
                done
            done
        done
        unusedVert[destination of ed] := φ
        add edge ed into the tree t
        add source of ed into usedVert
    done
End

উদাহরণ (C++)

#include 
#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];
    public:
    Tree(){ n = 0; }
    void addEdge(edge e){
        edges[n] = 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;
    for(i = 1; i < V; i++){
        usedVert[i] = -1;
        unusedVert[i] = i;
    }
    tr.n = 0;
    while(p != V){
        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){
                        min = costMat[i][j];
                        ed.u = i; ed.v = j; ed.cost = min;
                    }
                }
            }
        }
        unusedVert[ed.v] = -1;
        tr.addEdge(ed);
        usedVert[p] = ed.u; p++;
    }
}
int main(){
    Tree tr;
    prims(tr, 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)