एक कनेक्टेड ग्राफ 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
दो सेट परिभाषित करें: usedVert, unusedVert
usedVert[0] := start और unusedVert[0] := φ
स्टार्ट को छोड़कर सभी वर्टेक्स के लिए do
usedVert[i] := φ
unusedVert[i] := i //सभी वर्टेक्स को अनयूज्ड लिस्ट में जोड़ें
done
जबकि usedVert में वर्टेक्स की संख्या ≠ V do //V कुल नोड्स की संख्या है
min := ∞
usedVert ऐरे के सभी वर्टेक्स के लिए do
ग्राफ के सभी वर्टेक्स के लिए do
यदि min > cost[i,j] AND i ≠ j तो
min := cost[i,j]
ed := i और j के बीच एज, और ed की लागत := min
done
done
done
unusedVert[ed का डेस्टिनेशन] := φ
एज ed को ट्री t में जोड़ें
ed के सोर्स को 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]; //एक ट्री में वर्टेक्स-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 को अनयूज्ड वर्टेक्स से हटाएं tr.addEdge(ed); usedVert[p] = ed.u; p++; //u को यूज्ड वर्टेक्स में जोड़ें } } int main(){ Tree tr; prims(tr, 0); //प्रारंभिक नोड 0 tr.printEdges(); }
आउटपुट
Edge: A--B And Cost: 1 Edge: A--C And Cost: 3 Edge: A--D And Cost: 4 Edge: B--E And Cost: 2 Edge: F--E And Cost: 2 Edge: G--F And Cost: 3 Total Cost: 15
