प्रिम का न्यूनतम स्पैनिंग ट्री एल्गोरिदम

एक कनेक्टेड ग्राफ 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 
    unusedVert[destination of ed] := φ 
    add edge ed into the tree t 
    add source of ed into usedVert 
  done 
End

उदाहरण

#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]; //as a tree has vertex-1 edges public: Tree() { n = 0; } void addEdge(edge e) { edges[n] = e; //add edge e into the tree n++; } void printEdges() { //print edge, cost and total cost 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; //initialize usedVert[0] = start; p = 1; unusedVert[0] = -1; //-1 indicates the place is empty for(i = 1; i<V; i++) { usedVert[i] = -1; //all places except first is empty unusedVert[i] = i; //fill with vertices } tr.n = 0; //get edges and add to tree while(p != V) { //p is number of vertices in usedVert array 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) { //find the edge with minimum cost //such that u is considered and v is not considered yet min = costMat[i][j]; ed.u = i; ed.v = j; ed.cost = min; } } } } unusedVert[ed.v] = -1; //delete v from unusedVertex tr.addEdge(ed); usedVert[p] = ed.u; p++; //add u to usedVertex } } main() { Tree tr; prims(tr, 0); //starting node 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)