Skip to main content

PRIM’S ALGORITHM


#include<iostream.h>
#include<conio.h>
#define inf 333

class mst
{
int n,e,k,mincost,cost[10][10];
public:
mst()
{
n=0;
e=0;
k=0;
mincost=0;
}
void read();
void spantree();
void display();
};
void mst::read()
{
int i,j,z;
cout<<"Enter the no of Vertices\n";
cin>>n;
for(i=1;i<=n;i++)
cost[i][0]=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j]=inf;
cout<<"Enter the Cost Matrix\n";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cout<<"["<<i<<","<<j<<"]=";
cin>>z;
if(z)
{
cost[i][j]=cost[j][i]=z;
e++;
}
}
}

void mst::spantree()
{
int i,j,row,col,flag;
int min=inf;
cost[1][0]=1;
while(k<n-1 && e!=0)
{
flag=0;
min=inf;
for(i=1;i<=n;i++)
if(cost[i][0]==1)
{
for(j=1;j<=n;j++)
{
if(cost[j][0]==0 && cost[i][j]<min)
{
min=cost[i][j];
col=j;
flag=1;
}
}
}
if(flag)
{
k++;
mincost=mincost+min;
cost[col][0]=1;
e--;
}
}
}

void mst::display()
{
if(k!=n-1)
cout<<"No Spanning Tree\n";
else
cout<<"Cost Of MST: "<<mincost;
}
void main()
{
mst s;
clrscr();
cout<<"Minimum Spanning Tree\n\n";
s.read();
s.spantree();
s.display();
getch();
}

Labels:

Comments

Post a Comment

Popular posts from this blog

UDP SOCKETS CHAT APPLICATION (SERVER & CLIENT) USING C

SERVER #include<stdio.h> #include<netinet/in.h> #include<sys/types.h> #include<sys/socket.h> #include<netdb.h> #include<string.h> #include<stdlib.h> #define MAX 80 #define PORT 43454 #define SA struct sockaddr void func(int sockfd) { char buff[MAX]; int n,clen; struct sockaddr_in cli; clen=sizeof(cli); for(;;) { bzero(buff,MAX); recvfrom(sockfd,buff,sizeof(buff),0,(SA *)&cli,&clen); printf("From client %s To client",buff); bzero(buff,MAX); n=0; while((buff[n++]=getchar())!='\n'); sendto(sockfd,buff,sizeof(buff),0,(SA *)&cli,clen); if(strncmp("exit",buff,4)==0) { printf("Server Exit...\n"); break; } } } int main() { int sockfd; struct sockaddr_in servaddr; sockfd=socket(AF_INET,SOCK_DGRAM,0); if(sockfd==-1) { printf("socket creation failed...\n"); exit(0); } else printf("Socket successfully created..\n"); bzero(&servaddr,sizeof(s
5 comments
Read more

SIMULATION OF SLIDING WINDOW PROTOCOLS USING C

SENDER #include<sys/socket.h> #include<sys/types.h> #include<netinet/in.h> #include<netdb.h> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<unistd.h> #include<errno.h> int main() { int sock,bytes_received,connected,true=1,i=1,s,f=0,sin_size; char send_data[1024],data[1024],c,fr[30]=" "; struct sockaddr_in server_addr,client_addr; if((sock=socket(AF_INET,SOCK_STREAM,0))==-1) { perror("Socket not created"); exit(1); } if(setsockopt(sock,SOL_SOCKET,SO_REUSEADDR,&true,sizeof(int))==-1) { perror("Setsockopt"); exit(1); } server_addr.sin_family=AF_INET; server_addr.sin_port=htons(17000); server_addr.sin_addr.s_addr=INADDR_ANY; if(bind(sock,(struct sockaddr *)&server_addr,sizeof(struct sockaddr))==-1) { perror("Unable to bind"); exit(1); } if(listen(sock,5)==-1) { perror("Listen"); exit(1); } fflush(stdout); sin_size=sizeof(st
5 comments
Read more

TCP SOCKET DATE AND TIME USING C

SERVER #include<stdio.h> #include<sys/types.h> #include<sys/socket.h> #include<netinet/in.h> #include<time.h> #include<string.h> #include<stdlib.h> #define max 30 #define PORT 2100 int main() { int sersoc,clisoc,conn,len,wri; char str[max]; pid_t pid; time_t ticks; socklen_t clilen; struct sockaddr_in servaddr,cliaddr; servaddr.sin_family=AF_INET; servaddr.sin_port=htons(PORT); servaddr.sin_addr.s_addr=htonl(INADDR_ANY); if((sersoc=socket(AF_INET,SOCK_STREAM,0))<0) { perror("Socket Error"); exit(0); } if(bind(sersoc,(struct sockaddr *)&servaddr,sizeof(servaddr))<0) { perror("Bind Error"); exit(0); } listen(sersoc,10); for(;;) { len=sizeof(cliaddr); conn=(accept(sersoc,(struct sockaddr *)&clisoc,&len)); if((pid=fork())==0) { close(sersoc); ticks=time(NULL); strcpy(str,ctime(&ticks)); if(wri==(write(conn,str,sizeof(str),0))<0) { printf("Write Error");
3 comments
Read more