C program to compute minimum cost spanning tree

#include
#include
#define SIZE 20
#define INFINITY 32767
void prim(int G[][SIZE],int nodes)
{
int select [SIZE],i,j,k;
int min_dist,v1,v2,total=0;
for(i=0;i
select[i]=0;
printf("\n\n The minimal spanning tree is:\n");
select[0]=1;
for(k=1;k
{
min_dist=INFINITY;
for(i=0;i
{
for(j=0;j
{
if(G[i][j] && ((select[i] && !select[j])||(!select[i] && select[j])))
{
if(G[i][j]
{
min_dist=G[i][j];
v1=i;
v2=j;
}
}
}
}
printf("\n Edge(%d%d) & wt=%d",v1,v2,min_dist);
select[v1]=select[v2]=1;
total=total+min_dist;
}
printf("\n\n\t Total path length is=%d",total);
}
void main()
{
int G[SIZE][SIZE],nodes;
int v1,v2,length,i,j,n;
clrscr();
printf("\n\t Prim's algorithm\n");
printf("\n Enter no. of nodes in the graph");
scanf("%d", &nodes);
printf("\n enter no. of edges in the graph");
scanf("%d",&n);
for(i=0;i
G[i][j]=0;
printf("\n Enter edges & wts\n");
for(i=0;i
{
printf("\n Enter Edge by v1&v2:");
scanf("%d%d", &v1,&v2);
printf("\n enter corresponding wt:");
scanf("%d",&length);
G[v1][v2]=G[v2][v1]=length;
}
getch();
printf("\n\t");
clrscr();
prim(G,nodes);
getch();
}


OUTPUT:

enter the no of nodes in graph:7
enter the no of edges in graph:12

enter edges and weights

enter edges by v1 and v2:0 1
enter the corresponding weight 2

enter edges by v1 and v2:0 2
enter the corresponding weight 4

enter edges by v1 and v2:0 3
enter the corresponding weight 1

enter edges by v1 and v2:1 3
enter the corresponding weight 3

enter edges by v1 and v2:1 4
enter the corresponding weight 10

enter edges by v1 and v2:2 3
enter the corresponding weight 2

enter edges by v1 and v2:3 4
enter the corresponding weight 7
enter edges by v1 and v2:2 5
enter the corresponding weight 5

enter edges by v1 and v2:5 6
enter the corresponding weight 1

enter edges by v1 and v2:4 6
enter the corresponding weight 6

enter edges by v1 and v2:3 5
enter the corresponding weight 8

enter edges by v1 and v2:3 6
enter the corresponding weight 4

The minimal spanning tree is:
edge(0,1)&weight=2
edge(0,3)&weight=1
edge(2,3)&weight=2
edge(3,6)&weight=4
edge(4,6)&weight=6
edge(5,6)&weight=1

total path length is=16