C++ program for MST using Prims algorithm

C++ program for MST using Prims algorithm

#include <iostream>

using namespace std;

int main()

{

      int a,b,u,v,n,i,j,count=1;

      int visited[10]= {0},min,mincost=0,cost[10][10];

      cout<<"\nEnter the number of nodes:";

      cin>>n;

      cout<<"\nEnter the adjacency matrix:\n";

      for (i=0;i<n;i++)

      {

            for (j=0;j<n;j++)

            {

                  cin>>cost[i][j];

                  if(cost[i][j]==0)

                        cost[i][j]=999;  //replace all 0 with highest number

            }

      }

      visited[0]=1;

      cout<<"\n";

      while(count<n)

      {

            min=999;

            for(i=0;i<n;i++)// finding min. cost in matrix

            {

                  for (j=0;j<n;j++)

                  {

                        if(cost[i][j]<min)

                        {

                              if(visited[i]!=0)

                              {

                                    min=cost[i][j];

                                    a=u=i;

                                    b=v=j;

                              }

                        }

                  }

            }

            if(visited[u]==0 || visited[v]==0)

            {

                  cout<<"\nEdge"<<count++ <<" : " <<a<<"->"<<b<<" Cost= "<<min;

                  mincost+=min;

                  visited[b]=1;

            }

            cost[a][b]=cost[b][a]=999;  //replace processed min cost by highest number

      }

      cout<<"\nMinimun cost="<<mincost;

      return 0;

}

Output:

Enter the number of nodes:4

Enter the adjacency matrix:

0 5 1 4

0 0 0 3

0 2 0 0

0 0 3 0

Edge1 : 0->2 Cost= 1

Edge2 : 2->1 Cost= 2

Edge3 : 1->3 Cost= 3

Minimun cost=6