PRIMS-Greedy

 #include<iostream.h>  
 #include<conio.h>  
 class prims  
 {  
       private:  
             int i,j,k,l,close[50];  
             int cost[50][50],mincost,t[50][50];  
             int min_cost;  
       public:  
             void getdata(int n);  
             void printdata(int);  
             void prim_s(int n);  
 };  
 void prims::getdata(int n)  
 {  
      cout<<"\nEnter the cost of adjacency matrix";  
      cout<<"\n(If there is no edge then enter 9999)";  
      for(i=1;i<=n;i++)  
      {  
           for(int j=i;j<=n;j++)  
           {  
                if(i!=j)  
                {  
                     cout<<"\nCost between "<<i<<" and "<<j<<" : ";  
                     cin>>cost[i][j];  
                     cost[j][i]=cost[i][j];  
                }  
           }  
      }  
      k=1;  
      l=2;  
      for(i=1;i<=n;i++)  
      {  
           for(j=i;j<=n;j++)  
           {  
                if((i!=j)&&(cost[i][j]<cost[k][l]))  
                {  
                     k=i;  
                     l=j;  
                }  
           }  
      }  
 }  
 void prims::prim_s(int n)  
 {  
      mincost=cost[k][l];  
      t[1][1]=k;  
      t[1][2]=l;  
      for(i=1;i<=n;i++)  
      {  
           if(cost[i][l]<cost[k][i])  
                close[i]=l;  
           else  
                close[i]=k;  
      }  
      close[l]=0;  
      close[k]=0;  
      for(i=2;i<=n-1;i++)  
      {  
           min_cost=9999;  
           for(int a=1;a<=n;a++)  
           {  
                if((close[a]!=0)&&(min_cost>cost[a][close[a]]))  
                {  
                     j=a;  
                     min_cost=cost[j][close[j]];  
                }  
           }  
           t[i][1]=close[j];  
           t[i][2]=j;  
           mincost=mincost+min_cost;  
           close[j]=0;  
           for(k=1;k<=n;k++)  
           {  
                if((close[k]!=0)&&(cost[k][close[k]]>cost[k][j]))  
                     close[k]=j;  
           }  
      }  
 }  
 void prims::printdata(int n)  
 {  
      cout<<"\nMinimum Cost = "<<mincost;  
      cout<<"\nThe path is \n";  
      for(i=1;i<n;i++)  
           cout<<’\t’<<t[i][1]<<" to "<<t[i][2]<<"\n";  
 }  
 void main()  
 {  
      int n;  
      prims pr;  
      clrscr();  
      cout<<"\n\t\t\tPRIMS ALGORITHM";  
      cout<<"\nEnter the limit : ";  
      cin>>n;  
      pr.getdata(n);  
      pr.prim_s(n);  
      pr.printdata(n);  
      getch();  
 }