Prims algorithm using greedy method in C Programming

ALGORITHM

Prims algorithm using greedy method in C Programming

#include
#include

#define MAX 10
#define NOPATH 999


void fnPrims(int aiWei[MAX][MAX],int iSize)
{
int aiNear[MAX],iI,iJ,iCost=NOPATH,iK,iL,iM,iZ=1,iSmall;
static int min_cost,Sol[NOPATH][2];
for(iI=1;iI<=iSize;iI++)
for(iJ=1;iJ<=iSize;iJ++)
if(aiWei[iI][iJ]
{
iCost=aiWei[iI][iJ];
iK=iI;
iL=iJ;
}
Sol[1][1]=iK;
Sol[1][2]=iL;
min_cost=min_cost+iCost;
for(iJ=1;iJ<=iSize;iJ++)
aiNear[iJ]=999;
aiNear[iK]=0;
aiNear[iL]=0;
for(iI=1;iI<=iSize;iI++)
{
if(aiNear[iI]!=0)
{
if(aiWei[iL][iI]
aiNear[iI]=iL;
else
aiNear[iI]=iK;
}
}
printf("\nStep : 1");
printf("\n________");
for(iI=1;iI<=iSize;iI++)
printf("\naiNear[%d] = %d ",iI,aiNear[iI]);
for(iI=2;iI<=iSize-1;iI++)
{
iJ=1;
iSmall=999;
printf("Step : %d\n",iI);
printf("______________");
for(iM=1;iM<=iSize;iM++)
if(aiNear[iM]!=0)
{
printf("\naiWei[%d][%d]=%d",iM,aiNear[iM],aiWei[iM][aiNear[iM]]);
if(iSmall>aiWei[iM][aiNear[iM]])
{
iJ=iM;
iSmall=aiWei[iM][aiNear[iM]];
}
}
getch();
Sol[iI][1]= iJ;
printf("\nThe iJ value : %d\n",iJ);
Sol[iI][2]=aiNear[iJ];
printf("\nCost is : %d",aiWei[iJ][aiNear[iJ]]);
min_cost=min_cost+aiWei[iJ][aiNear[iJ]];
printf("\nMinimum Cost : %d\n",min_cost);
aiNear[iJ]=0;
for(iM=1;iM<=iSize;iM++)
{
if(aiNear[iM]!=0)
if(aiWei[iM][iJ]
aiNear[iM]=iJ;
}
}
if(min_cost>=NOPATH)
printf("\nNOT SPANNING TREE");
else
{
printf("\nPaths are : \n");
for(iI=1;iI
{
for(iJ=1;iJ<3;ij++)
printf(" %d ",Sol[iI][iJ]);
printf("\n");
}
printf("\nThe cost is : %d",min_cost);
}
}

void main()
{
int iSize,iI,iJ,aiWei[MAX][MAX];
clrscr();
printf("\n\tPRIMS ALGORITHM");
printf("\nEnter the no vertices : ");
scanf("%d",&iSize);
printf("\nEnter the Weighted matrix.\n");
for(iI=1;iI<=iSize;iI++)
for(iJ=1;iJ<=iSize;iJ++)
scanf("%d",&aiWei[iI][iJ]);
fnPrims(aiWei,iSize);
getch();
}



/*

OUTPUT:

PRIMS ALGORITHM
Enter the no vertices : 5

Enter the Weighted matrix.
999 4 8 999 999
4 999 6 999 2
8 6 999 1 5
999 999 1 999 3
999 2 5 3 999

Step : 1
________
aiNear[1] = 3
aiNear[2] = 3
aiNear[3] = 0
aiNear[4] = 0
aiNear[5] = 4 Step : 2
______________
aiWei[1][3]=8
aiWei[2][3]=6
aiWei[5][4]=3

The iJ value :5

Cost is : 3
Minimum Cost : 4
Step : 3
______________
aiWei[1][3]=8
aiWei[2][5]=2
The iJ value : 2

Cost is : 2
Minimum Cost : 6
Step : 4
______________
aiWei[1][2]=4
The iJ value : 1

Cost is : 4
Minimum Cost : 10

Paths are :
3 4
5 4
2 5
1 2

The cost is : 10

*/