#include<stdio.h>
#include<conio.h>
int g[20][20],d[20],visited[20],p[20];
int v,e;
int i,j;
void creategraph();
void prim();
void main()
{
clrscr();
creategraph();
prim();
getch();
}
void creategraph()
{
int a,b,w;
printf("Enter number of vertices:");
scanf("%d",&v);
printf("Enter number of edges:");
scanf("%d",&e);
for(i=1;i<=v;i++)
for(j=1;j<=v;j++)
g[i][j]=0;
for(i=1;i<=v;i++)
p[i]=0;
visited[i]=0;
d[i]=32767;
for(i=1;i<=e;i++)
{
printf("Enter edges a,b and w:");
scanf("%d%d%d",&a,&b,&w);
g[a][b]=g[b][a]=w;
}
}
void prim()
{
int current=1,totalvisited=1,min,mincost=0;
visited[current]=1;
d[current]=0;
while(totalvisited!=v)
{
for(i=1;i<=v;i++)
{
if(g[current][i]!=0)
if(visited[i]==0)
if(d[i]>g[current][i])
{
}
}
min=32767;
for(i=1;i<=v;i++)
{
d[i]=g[current][i];
p[i]=current;
if(visited[i]==0)
if(d[i]<min)
{
min=d[i];
current=i;
}
}
visited[current]=1;
totalvisited++;
}
for(i=1;i<=v;i++)
mincost=mincost+d[i];
printf("Minimum cost of the spanning tree is %d",mincost);
}
OutPut:
Enter number of vertices : 3
Enter number of edges : 3
Enter edges a , b &w: 1 2 10
Enter edges a , b &w: 2 3 20
Enter edges a , b &w: 3 1 30
Minimum cost of the spanning tree is 30
