MINIMUM SPANNING TREE-PRIM'S ALGORITHM IN C++

PROGRAM CODING:

#include<iostream>

#include<string.h>

#include<stdlib.h>

#include<conio.h>

using namespace std;

# define INFI 10000

class point

{ public:

char *pt;

int n;

point()

{ cout<<"\nEnter the no of vertices: ";

cin>>n;

pt=(char *)new char[n];}

void read();};

class arc:public point

{ public:

int a[10][10];

int i,j,c;

void read_mat();

void disp_mat();};

class graph:public arc

{ public:

int k[10],d[10],i,s,sum,min,j,m,c;

char *p;

public:

graph()

{ i=0;s=0;sum=0;min=-1;

p=(char *)new char[n];}

void mst(char s);};

void point::read()

{ cout<<"\nEnter the vertices name: ";

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

cin>>pt[i];}

void arc::read_mat()

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

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

{ if(i==j)

a[i][j]=0;

else

a[i][j]=INFI;}

cout<<"\nEnter the distance between vertices(100 if no connection)\n";

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

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

{ if(a[i][j]>100)

{ cout<<pt[i]<<" & "<<pt[j]<<": ";

cin>>a[i][j]; }

a[j][i]=a[i][j]; } }}

void arc::disp_mat()

{ cout<<"\n ADJACENCY MATRIX\n";

cout<<"=\t";

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

cout<<pt[i]<<"\t";

cout<<"\n\n";

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

{ cout<<pt[i]<<"\t";

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

cout<<a[i][j]<<"\t";

cout<<"\n\n";}

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

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

if(a[i][j]==100||a[i][j]==0)

c++;

if(c==n)

cout<<"\nGRAPH IS NOT CONNECTED";}

void graph::mst(char ii)

{ int c,check=0;

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

{ if(pt[s]==ii)

{ check=1;

break;} }

if(check==1)

{ m=s;

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

{ k[c]=0;

if(c==s)

d[c]=0;

else

d[c]=INFI;

p[c]='0';}

while(i<=n)

{ cout<<"\nVERTEX\tKNOWN\tDISTANCE\tPREVIOUS\n";

k[s]=1;

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

{ if((a[s][j]!=0||a[s][j]!=INFI)&&(k[i]!=1))

{ if((d[j]>a[s][j])&&(s!=j))

{ d[j]=a[s][j];

p[j]=pt[s];}}}

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

cout<<pt[j]<<"\t"<<k[j]<<"\t"<<d[j]<<"\t\t"<<p[j]<<endl;

cout<<"\n\n";

for(j=0,min=1000;d[j]!=0,j<n;j++)

{ if((min>d[j])&&(k[j]!=1))

{ min=d[j];

s=j;

}}

i++;}

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

{

if(d[j]!=INFI)

sum+=d[j];}

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

{ if(j!=m)

cout<<"\nCost from "<<pt[j]<<" to "<<p[j]<<" is: "<<d[j];

cout<<"\n";}

cout<<"\nMaximum Cost from \t"<<pt[m]<<"\t is"<<sum<<endl;}

else

cout<<"\nThe vertex is not found";}

main()

{ char ii;

graph g;

g.read();

g.read_mat();

g.disp_mat();

cout<<"\nEnter the Starting Point:";

cin>>ii;

g.mst(ii);

getch();

}