सी ++ में प्राइम का एल्गोरिदम (आसन्न मैट्रिक्स प्रतिनिधित्व के लिए सरल कार्यान्वयन)

प्राइम का एल्गोरिदम एक लालची विधि है जिसका उपयोग किसी दिए गए भारित अप्रत्यक्ष ग्राफ के लिए न्यूनतम फैले हुए पेड़ को खोजने के लिए किया जाता है।

भारित ग्राफ़ एक ऐसा ग्राफ़ है जिसमें वज़न मान के साथ सभी किनारे होते हैं।

अप्रत्यक्ष ग्राफ़ एक विशेष प्रकार का ग्राफ है जिसमें सभी किनारे द्विदिश होते हैं।

न्यूनतम फैले हुए पेड़ एक उपसमुच्चय है जिसमें सभी किनारे और शीर्ष होते हैं लेकिन कोई चक्र नहीं होता है और इसका कुल किनारे का वजन कम से कम होता है।

इस लेख में, हम न्यूनतम फैले हुए पेड़ को खोजने के लिए प्राइम के एल्गोरिथ्म के बारे में जानेंगे। आमतौर पर, एल्गोरिथ्म दो सरणियों का उपयोग करता है लेकिन इस समाधान में, हम केवल एक का उपयोग करेंगे।

प्राइम एल्गोरिथ्म के कार्यान्वयन को दिखाने के लिए कार्यक्रम।

उदाहरण

#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] == false && inMST[v] == false)
      return false;
   else if (inMST[u] == true && inMST[v] == true)
      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) {
               if (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;
}

आउटपुट

The Minimum spanning tree for the given tree is :
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