// Prims Program in C language
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define size 8
int cost[size][size]={0},n=0;
/*
The get_mat function-for creating the adjacency matrix
Input :none
Output:none
Parameter Passing Method :none
Called By : main()
Calls : none
*/
void get_mat()
{
int i,j,v1,v2,wt;
for(i=0;i<=size;i++)
for(j=0;j<=size;j++)
cost[i][j]=1000;
printf("enter no of vertices: ");
scanf("%d",&n);
do{
printf("\nenter edge & cores wt (v1<->v2,wt): ");
scanf("%d%d%d",&v1,&v2,&wt);
cost[v1][v2]=cost[v2][v1]=wt;
printf("\ncontinue(y/n): ");
fflush(stdin);
}while(getche()=='y');
}
/*
The main function
Input :none
Output:none
Called By : O.S.
Calls :get_mat()
*/
void main()
{
int t[size]={0},wt[size]={0},min,p,sum=0,temp,i,j,k=0,l=0,m=0;
get_mat();
t[1]=1;
printf("\n\ntree includes following edges:");
for(p=1;p<=n-1;p++)
{
temp=1000; /sort of infinity distance/
for(i=1;i<=n;i++)
{
if(t[i]==1)
{
min=1000;
for(j=1;j<=n;j++)
{
if(cost[i][j]<min&&t[j]==0)
{
min=cost[i][j]; /checking the minimum cost/
k=j;
} /* End Of if*/
} /End Of for/
if(min<temp)
{
temp=min;
l=k;m=i;
} /end of if/
}
}
wt[p]=cost[m][l]; /storing the minimum wt from the graph/
sum=sum+wt[p]; /finding total cost of min.spanning tree/
printf("\n\nedge: %d<-->%d wt: %d",m,l,cost[m][l]);
t[l]=t[m]=1;
}
printf("\n\nwt of minimum spanning tree: %d",sum);
getch();
}
/*End Of Program/