prim.cpp

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
int v[10],e[10][10],w[10][10],n,mincost;
void Prim()
{

  v[1]=1;
  for(int i=1;i<=n;i++)
    {
      int min=32767,t1=0,t2=0;
      for(int k=1;k<=n;k++)
      for(int j=1;j<=n;j++)
	if(w[k][j]<min && v[k] && !v[j])
	    {
	     min=w[k][j];
	     t1=k;t2=j;
	    }
	    e[t1][t2]=1;
	    v[t2]=1;
       mincost+=w[t1][t2];
     }

}

void main()
{
 clrscr();
 int i,j;
 cout<<"\n Enter the value of n i.e., no of vertices:\t";cin>>n;
 cout<<"\n Enter the weight connected graph:\n";
 cout<<"\n Enter upper triangle only.\n";
 for( i=1;i<=n;i++)
 for( j=i+1;j<=n;j++)
  {
   cin>>w[i][j];
   w[j][i]= w[i][j];
  }
 Prim();
 cout<<"\n Edges in the minimum cost spanning tree:\n";
 for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
 if(e[i][j])
  cout<<"\n"<<i<<"->"<<j;
 getch();
}